3. 普及组算法部分 - dp动态规划(一) - 《信息学奥赛21天突破》

概念

Dynamic Programming is a technique that combines the correctness of complete search and the efficiency of greedy algorithms. Dynamic Programming can be applied if the problem can be divided into overlapping subproblems that can be solved independently.There are two uses for Dynamic Programming:

Finding an optimal solution: We want to find a solution that is as large as possible or as small as possible.
Counting the number of solutions: We want to calculate the total number of possible solutions.

Understanding dynamic programming is a milestone in every competitive programmer’s career. While the basic idea is simple, the challenge is how to apply dynamic programming to different problems.

The dynamic programming algorithm is based on a recursive function that goes through all possibilities how to form the sum, like a brute force algorithm. However, the dynamic programming algorithm is efficient because it uses memoization and calculates the answer to each subproblem only once.

Recursive formulation，再看硬币问题

贪心算法的策略是每次取最大值，但并不是每一次都有效。我们下面看看，

反例，背包体积是10，有三个物品体积9，价值100 体积3，价值60 体积7，价值70

如果是贪心，优先选择价值100的，占用9体积，就不能选其他了如果是dp，选择体积是3+7的方案，获得价值130

// 代码如下，但这个写法不是很高效(加上记忆化就好了)
int solve(int x) {
    if (x < 0) return INF;  //INF代表一个无穷大的值
    if (x == 0) return 0;
    int best = INF;
    for (auto c : coins){   //枚举可以使用的硬币 这是C++11的写法
       best = min(best, solve(x-c)+1);
    }
    return best;
}

Using memoization，记忆化

//下面就是加记忆化的写法
//The time complexity of the algorithm is O(nk), 
//where n is the target sum and k is the number of coins.
//题目背景，凑够n元，最少需要几枚硬币
int solve(int x) {
    if (x < 0) return INF;
    if (x == 0) return 0;
    if (ready[x]) return value[x];
    int best = INF;
    for (auto c : coins) {
       best = min(best, solve(x-c)+1);
    }
    value[x] = best;
    ready[x] = true;
    return best;
}
//这份代码，并不是模板，理解明白就行

// 下面是循环的写法
value[0] = 0;
for (int x = 1; x <= n; x++) {     //枚举sum
    value[x] = INF;
    for (auto c : coins) {         //枚举硬币 
       if (x-c >= 0) {
           value[x] = min(value[x], value[x-c]+1);
        } 
    }
}
// 这份代码，并不是模板，理解明白就行
// value[n]

关于记忆化的补充：

When we solve a recursive problem that its sub-problems overlaps(重叠), hence calling sub-problems. More than once and repeating its calculation in nature that typically makes the order exponentials!

When the original space is small enough to be memorized, then saving these sub-problems makes order small too, as sub-problems calculated once.

// Fibonacci Series: 
// Fib(n) = fib(n-1) + fib(n-2).    
// Fib(0) = fib(1) = 1
int fib(int n)
{
    if(n <= 1)
        return 1;
    return fib(n-2) + fib(n-1);
}

Let’s SAVE the answer, and let space of N is called 2N times!

int savedAnswers[MAX];        // Initialized to -1, means no answer
int fibSave(int n)
{
    if(n <= 1)
        return 1;
    if(savedAnswers[n] != -1)
        return savedAnswers[n];
    return savedAnswers[n] = fib(n-2) + fib(n-1);
// O(N) Search space, hence O(N) memory -> O(N) Order!

General Rules:
1- Recursive Function
2- Sub-calls Overlap
3- Small Search Space, so putting in memory is doable

加记忆化的例子，【Luogu P5017】Noip2018-T3 摆渡车题解

接下来加记忆化。其实在写记忆化搜索的时候，我个人认为加记忆化是最简单的，只要爆搜写好并且写对，加记忆化易如反掌。哪里有 return ，哪里加记忆化。最后代码如下（由于其余部分相同，这里只给出 dfs 代码）

加记忆化的例子，聊聊动态规划与记忆化搜索【特别经典】

不依赖任何 外部变量
答案以返回值的形式存在, 而不能以参数的形式存在(就是不能将 dfs 定义成 dfs(pos ,tleft , nowans ), 这里面的 nowans 不符合要求).
对于相同一组参数, dfs 返回值总是相同的

加记忆化方法总结：

写出这道题的暴搜程序(最好是dfs)
将这个dfs改成”无需外部变量”的dfs
添加记忆化数组

DP need good recursive mentality, that views answer in term of recursion! So develop your skills! Many DPs follow a certain pattern (style), we will investigate some of them.

分治与dp的区别

Do we need to apply DP for merge sort? NEVER, a call will never be repeated! like most of Divide-and-Conquer Algorithm.

分治与dp，两者都是将问题划分为子问题，然后求解子问题。
当子问题不会被求解多次的时候，应该用分治；被求解多次的，就dp。
例如，二叉查找，用分治；求fibo，用dp。

Dynamic Programming most typical cases: Minimization, Maximization and Counting. But could have adhock usages. In fact, above code is not called DP, it is call Memoization (NOT Memorization). It is a technique when we have a recusive function and save calls).

DP is to build bottom up according to recurrence while Memoization is top-down.

int dp_fib(int n)
{
    int fib[MAX];
    fib[0] = fib[1] = 1;    // base case
    for(int i = 2; i <= n; ++i)
        fib[i] = fib[i-1] + fib[i-2];    // bottom up according to recurrence
    return fib[n];
}

Writing Memoization is much more natural, although there are cases when DP is a must.

01背包问题(递归)

// 问题描述：
// 重量，W: 10, 4 , 20, 5, 7
// 价值，P: 10, 15, 3 , 1, 4
// knapsack size = 12
// 最佳方案：0   1   0   0  1
const int MAX = 5;
int n = 5;
int weights[MAX] = {10, 4, 20, 5, 7};
int benfit[MAX] = {10, 15, 3, 1, 4};
// called with knapsack(0, intialWeight)
int knapsack(int i, int reminder)    // aka(also known as) 0/1 knapsack
{
    if(i == n)
        return 0;
    int choice1 = knapsack(i+1, reminder);
    int choice2 = 0;
    if(reminder >= weights[i])
        choice2 = knapsack(i+1, reminder - weights[i]) + benfit[i];
    return max(choice1, choice2);
}
//这个版本还需要加上记忆化，待完善

Constructing a solution打印方案(循环,递归)

dp问题当中，有很多情况，不仅让你求最值，还让你输出最值情况下的方案是什么（如果有多种方案，输出一种即可，oj会做special judge）

//we can declare another array that indicates for each sum of money 
//the first coin in an optimal solution:
value[0] = 0;
for (int x = 1; x <= n; x++) {      //枚举体积
    value[x] = INF;
    for (auto c : coins) {          //枚举硬币
       if (x-c >= 0 && value[x-c]+1 < value[x]) {
           value[x] = value[x-c]+1;
           first[x] = c;
        }
    }
}
//输出方案
while (n > 0) {
    cout << first[n] << "\n";
    n -= first[n];
}

#include <iostream>
using namespace std;
int n, m, a[15];
int value[15];
int first[15];
int main()
{
    memset(value, 0x3f, sizeof value);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    value[0] = 0;
    for (int x = 1; x <= m; x++){            //枚举体积
        for (int i = 1; i <= n; i++)         //枚举硬币
            if (x - a[i] >= 0 && value[x - a[i]] + 1 < value[x]){
                value[x] = value[x - a[i]] + 1;
                first[x] = a[i];            //记录方案
            }
    }
    int sum = m;
    while (sum > 0){
        cout << first[sum] << ' ';
        sum -= first[sum];
    }
    puts("");
    return 0;
}
/*
3 10
1 3 4
*/

输出方案，我们更多的，还可以用递归输出

void print(int x)
{
    if (x == 0) return ;
    printf("%d ", first[x]); //这两行的顺序，决定了先递归再输出当前，还是先输出当前，再递归
    print(x - first[x]);
}
int main()
{
    //..........
    print(10);
    puts("");
    return 0;
}

#include <iostream>
using namespace std;
int n, m, a[15];
int value[15];
int first[15];
void print(int x)
{
    if (x == 0) return ;
    printf("%d ", first[x]);
    print(x - first[x]);
}
int main()
{
    memset(value, 0x3f, sizeof value);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    value[0] = 0;
    for (int x = 1; x <= m; x++){            //枚举体积
        for (int i = 1; i <= n; i++)         //枚举硬币
            if (x - a[i] >= 0 && value[x - a[i]] + 1 < value[x]){
                value[x] = value[x - a[i]] + 1;
                first[x] = a[i];            //记录方案
            }
    }
    print(m);
    puts("");
    return 0;
}
/*
3 10
1 3 4
*/

Counting the number of solutions统计方案个数

count[0] = 1;
for (int x = 1; x <= n; x++) {     //枚举sum
    for (auto c : coins) {         //枚举硬币
       if (x-c >= 0) {
           count[x] += count[x-c];
           //count[x] %= m;
       }
    } 
}

#include <iostream>
using namespace std;
int n, m, a[15];
int value[15];
int cnt[15];
int main()
{
    memset(value, 0x3f, sizeof value);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cnt[0] = 1;                              //体积为0有一种方案
    for (int x = 1; x <= m; x++){            //枚举sum，从小到大枚举
        for (int i = 1; i <= n; i++)         //枚举硬币
            if (x - a[i] >= 0){
                cnt[x] += cnt[x - a[i]];
            }
    }
    cout << cnt[m] << '\n';
    return 0;
}
/*
输入
3 5
1 3 4
输出
6
*/

— Now we have discussed all basic ideas of dynamic programming.

更多的示例

// 记忆化更多的例子
// Let's move to some other examples! Remember:
// Given grid of positive numbers, Start from 0, 0 and end at n, n. Move only to right and down - find path with sum of numbers is maximum.
/*
15
24
512
678
149
What paths there" 51289, 51789, 51749, 56789, 56749, 56149 ..
                  It is like: 5 { 1 {289, 789, 749}, 6{789, 749, 149} }
                  In other words, 5 needs answer of 1 and of 6 to maximize over them.
*/
int grid[MAX][MAX];
// Think in function F(i, j) that find solution from (i, j) to (n, n)
int maxPathSum(int r, int c)
{
    if( !valid(r, c))
        return 0;
    if (r == n-1 && c == n-1)
        return grid[r][c];    // base
    int path1 = maxPathSum(r, c+1);    // right
    int path2 = maxPathSum(r+1, c);    // down
    return grid[r][c] + max(path1, path2);
}
// How to trun code to memization?
// 1- Create array of input dimensions, and output of its return.
// E.g. int mem[MAX][MAX];
// Initialize it with a value that will never be a correct answer, e.g. -1
// If value is -1, then it is not visited before. Else, use saved value
int mem[MAX][MAX];    // R & C is in range N. Function return int
int maxPathSum_save(int r, int c)
{
    //1- Always hanle invalid calls first
    if( !valid(r, c))
        return 0;
    //2- Handle Base cases
    if (r == n-1 && c == n-1)
        return grid[r][c];    // base
    //3- check if visited before
    if(mem[r][c] != -1)
        return mem[r][c];
    int path1 = maxPathSum_save(r, c+1);    // right
    int path2 = maxPathSum_save(r+1, c);    // down
    return mem[r][c] = grid[r][c] + max(path1, path2);
}

/*
 Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence,
      thus deriving different arithmetical expressions that evaluate to different values. Let us, for example,
      take the sequence: 17, 5, -21, 15. There are eight possible expressions:
17    +    5    +    -21    +    15    =    16
17    +    5    +    -21    -    15    =    -14
17    +    5    -    -21    +    15    =    58
17    +    5    -    -21    -    15    =    28
17    -    5    +    -21    +    15    =    6
17    -    5    +    -21    -    15    =    -24
17    -    5    -    -21    +    15    =    48
17    -    5    -    -21    -    15    =    18
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the
sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.
You are to write a program that will determine divisibility of sequence of integers.
*/
// called with tryAll1(1, v[0])        // e.g. tryAll1(1, 17)
int tryAll1(int i, int sum) {
    if (i == n)
        return sum % k == 0;
    if (tryAll1(i + 1, sum + v[i]) || tryAll1(i + 1, sum - v[i])    )
        return 1;
    return 0;
}
/////////////////////////////////////////////////
int fix(int a) {
    return (a % k + k) % k;
}
int tryAll2(int i, int mod) {
    int &ret = mem[i][mod];
    if (ret != -1)
        return ret;
    if (i == n)
        return ret = mod == 0;
    if (tryAll2(i + 1, fix(mod + v[i])) || tryAll2(i + 1, fix(mod - v[i])))
        return ret = 1;
    return ret = 0;
}

TC: RGBStreet
http://community.topcoder.com/stat?c=problem_statement&pm=6680
const int MAX = 21;
int r[MAX];
int g[MAX];
int b[MAX];
int n;
const int OO = (int)1e6;
int mem[MAX][4];
int minCost(int i, int lasColor)
{
    if(i == n)
        return 0;
    int &ret = mem[i][lasColor];  //注意这个写法
    if(ret != -1)
        return ret;
    ret = OO;
    if(lasColor != 0)
        ret = min(ret, r[i] + minCost(i+1, 0));
    if(lasColor != 1)
        ret = min(ret, g[i] + minCost(i+1, 1));
    if(lasColor != 2)
        ret = min(ret, b[i] + minCost(i+1, 2));
    return ret;
}
class RGBStreet {
public:
    int estimateCost(vector <string> houses)
    {
        rep(i, houses)
        {
            istringstream iss(houses[i]);
            iss>>r[i]>>g[i]>>b[i];
        }
        n = sz(houses);
        clr(mem, -1);
        return minCost(0, 3);
    }
};

《一本通》题目

【例9.2】数字金字塔

//数字三角形模型

【例9.3】求最长不下降序列

//LIS

【例9.4】拦截导弹(Noip1999)

//LIS

【例9.5】城市交通路网

//LIS

【例9.6】挖地雷

//LIS

【例9.7】友好城市

//LIS

【例9.8】合唱队形

//LIS

【例9.9】最长公共子序列

//LCS

【例9.10】机器分配

//dp[i][j]前i个公司，分配j台设备的最大价值
//递归打印方案，这个输出方案的方案，需要多学习

最长上升子序列

//LIS

最大子矩阵

//最大子段和 + 前缀和，O(n^3)

登山

//LIS

摘花生

//数字三角形模型

最大上升子序列和

//LIS

怪盗基德的滑翔翼

//LIS

最低通行费

//LIS

三角形最佳路径问题

//数字三角形模型

拦截导弹

//LIS
//如果要拦截所有导弹最少要配备多少套这种导弹拦截系统

【例9.11】01背包问题

//01背包

【例9.12】完全背包问题

//完全背包

【例9.13】庆功会

//多重背包

【例9.14】混合背包

//混合背包

【例9.15】潜水员

//这个题目注意一个瓶子里的氧气和氮气，不是完整的用，可以只用一部分从而满足工作需要。

https://www.acwing.com/solution/content/7438/

背包问题中体积至多是 j ，恰好是 j ，至少是 j 的初始化问题的研究

【例9.16】分组背包

//分组背包，每组里只能选一个物品

【例9.17】货币系统

//完全背包，求方案数

采药

//01背包，noip原题

数字组合

//01背包，求方案数

宠物小精灵之收服

//小智的精灵球数量和皮卡丘的初始体力
//二维费用背包
//输出，收服C个小精灵时皮卡丘的剩余体力值最多为R。这个最后输出剩余体力值的方法也很聪明

买书

//完全背包，求方案数
//和 数字组合 ，比较像

Charm Bracelet

//01背包

装箱问题

//任取若干个装入箱内，使箱子的剩余空间为最小
//01背包，输出V-dp[V]

开餐馆

//LIS模型，i接在1..i-1谁后面的时候，注意判断距离问题

【例9.18】合并石子

//区间dp

【例9.19】乘积最大

//int dp[N][M]; //前i个数，插入了j个乘号
//先预处理出来数字的问题，更好一些

https://www.acwing.com/solution/content/18940/

【例9.20】编辑距离

//编辑距离，经典问题

【例9.21】方格取数

//从左上走到右下，走了两次，问能取到的最大值
//定义一个四维的状态，dp[N][N][N][N]，经过发现，可以优化到三维

【例9.22】复制书稿(book)

//输出具体方案，用了一个贪心的策略去设计输出答案的过程
//以下两种设计都可行，请体验体验
//设计状态dp[i][j] i个人，抄前j本书的复制时间
//设计状态dp[i][j] i个本书，有前j个人去抄

【例9.23】橱窗布置(flower)

//dp[i][j] 前i朵花插在前j个花瓶里

【例9.24】滑雪

//记忆化

公共子序列

//LCS

计算字符串距离

//编辑距离

糖果

//《1195：判断整除》这道递推类似，请回忆。

鸡蛋的硬度

//特别经典的一道题目，很难的，基本自己想不出来的，可以思考二十分钟试一试
//有两种设计状态的方法
//dp[i][j] 测量长度i层楼，用j个鸡蛋，最坏情况下需要扔的次数，O(n^2*m)
//dp[i][j] 用j个鸡蛋测i次，最多能测量的区间长度，O(nm)

大盗阿福

//从一个商店，可以被盗，也可以不被盗的两种情况入手，思考状态的设计dp[N][2]
//还有一种思路，线性dp的思路，状态只有一维，类似最大字段和的O(n)操作

股票买卖

//dp，状态机模型
//ybt的第8个测试点，跑起来不稳定，有可能会TLE这个点
//dp[N][3][2]; //dp(i,j,0)第i天，买卖j次，当前没有股票；dp(i,j,1)当前有股票

鸣人的影分身

//分苹果->鸣人的影分身->数的划分
//本题可以从分苹果入手，实现记忆化搜索的版本
//然后，再改成循环版本
//最后，再重新的，从集合角度出发，分析 (最小值为0 | 最小值不为0) 的推导过程

数的划分

//先从鸣人的影分身，变形一下，实现第一个版本，trick一下就可以
//重新的，从集合角度出发，分析(.... | .....)

Maximum sum

//这段题目求的是，两个不重合的最大子段和
//最大子段和，这个会写的
//如何表示两个不重合的最大子段和呢？ 多画图看一看就会找到线索

最长公共子上升序列

//LIS+LCS，非常好的题目，这个题面还要求输出方案。
//有O(n^4), O(n^3), O(n^2)的写法，都需要深入思考，琢磨实现