2020-08-11[日三省吾身]动态规划主题刷题记录

前排感谢labuladong大佬的模板，大多数分析是摘录其公众号文章！强推

应用场景

动态规划基本方程包含了三个条件，一状态转移方程，二最优值函数，三边界条件。状态转移方程就是动态过程的“动力”，我们在知道了k阶段的状态和决策后就可以得到k+1阶段的状态(反之同理)，它把各个阶段联系起来了，因而我们才可以从边界条件通过递推得到最优解。
动态规划的应用场景为求最值，运筹学中的一种最优化的方法。——核心为穷举，将所有可行的答案穷举出来，然后在其中找最值。

动态规划问题的穷举比较特殊，一般这类问题存在重叠子问题，暴力穷举的效率会十分低下，就需要备忘录和DP table来优化穷举过程。
动态规划问题一定会具备最优子结构，才能通过子问题的最值得到原问题的最值。
为保证正确的穷举，必须列出正确的状态转移方程。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划的三要素。其中状态转移方程是最难的，可以通过这样的思维框架来帮助思考：

明确[状态] -> 定义dp数组/函数的含义 -> 明确[选择] -> 明确 base case

递归算法时间复杂度

子问题的个数乘以解决一个子问题需要的时间。
但凡遇到递归问题最好都画出递归树辅助分析算法复杂度，帮助寻找低效的原因
子问题的个数即为递归树中节点的总数，二叉树节点总数为指数级别（爆炸），所以子问题个数为 $O(2^n)$ 。
解决一个子问题的时间，例如一次加法运算为 $O(1)$ 。
一般算法低效的问题在于：存在大量的重复计算——重叠子问题。

重叠子问题解法

暴力递归——导致低效
备忘录

备忘录的思路是：每次算出子问题的答案后先记到备忘录中再返回；每次遇到一个子问题先去备忘录中查询一下，如果已经解决过了就直接取出答案使用，避免耗时计算。
一般使用数组或者哈希表（字典）
备忘录的方法之前有些题目中也有用到，用于判断是否重复较有效。这种方法从递归树图上看效果等同于剪枝函数。是一种自顶而下的方法，没有了冗余的复杂计算，算法的时间复杂度可以降至 $O(n)$ 。

动态规划——自底而上

自顶而下：从一个较大规模的问题向下逐渐分解规模直到分解至最小可解子问题单元(递归树)；
自底而上:从问题规模最小的（base case）往上推，直到得到目标值
自底而上即为动态规划的思维，动态规划一般都脱离了递归，由循环迭代完成计算。
大部分情况下，2.3项效率基本相同

#include <iostream>
#include <vector>
#include <time.h>
using namespace std;
#define NUM 40

//暴力法
int fib1(int N) {
    if (N == 1 || N == 2) return 1;
    return fib1(N - 1) + fib1(N - 2);
}

//备忘录
int helper(vector<int>& memo, int n);
int fib2(int N) {
    if (N < 1) return 0;
    // 备忘录全初始化为 0
    vector<int> memo(N + 1, 0);
    // 初始化最简情况
    return helper(memo, N);
}
int helper(vector<int>& memo, int n) {
    // base case
    if (n == 1 || n == 2) return 1;
    // 已经计算过
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) +
        helper(memo, n - 2);
    return memo[n];
}

//DP table
int fib3(int N) {
    vector<int> dp(N + 1, 0);
    // base case
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[N];
}

void main()
{
    time_t start,end1,end2,end3;
    start = clock();
    cout << fib1(NUM) << endl;
    end1 = clock();
    cout<< (double)(end1 - start) / CLK_TCK <<endl;
    cout << fib2(NUM) << endl;
    end2 = clock();
    cout << (double)(end2 - end1) / CLK_TCK << endl;
    cout << fib3(NUM) << endl;
    end3 = clock();
    cout << (double)(end3 - end2) / CLK_TCK << endl;
    system("pause");
}
/*输出：
102334155
0.296
102334155
0.001
102334155
0
*/

细节优化

暴力解是动态规划问题的核心，即写出状态转移方程。优化方法则为上述2.3
在斐波那契数列问题中，由于当前状态仅与之前的两个状态有关，因此只需要储存之前两个状态就可以。这样，算法的空间复杂度就可以降为 $O(1)$ 。

但菲波那切数列不算是严格意义上的动态规划问题，因为不是在求最值。

最优子结构

要符合「最优子结构」，子问题必须相互独立。
列出正确的状态方程的思路：先确定状态，即原问题和子问题中变化的量；再确定dp函数的定义，dp（x）；然后确定选择并择优，也就是对于每个状态，可以做出什么选择改变当前状态。

[322] 零钱兑换

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //dp array
        vector<int> dp(amount+1,amount+1);//初始化dp数组,定义为dp[amount],即凑成amount
        //base case
        dp[0] = 0;
        for(int n=0;n<dp.size();n++)//自底而上
        {
            for (auto coin:coins)
            {
                if((n-coin)<0) continue; //子问题无解，跳过
                dp[n]= min(dp[n],1+dp[n-coin]);
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
};

总结

动态规划的核心问题就是如何穷举——即建立状态转移方程：先确定状态，再确定选择（改变状态），最后优化。很多穷举问题需要递归实现并且要确保解空间穷举完整。初次之外的备忘录和DP table仅仅只是用于优化穷举，用空间换时间。

[518]零钱兑换II

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        //dp array
        vector<int> dp(amount+1,0);//初始化dp数组,定义为dp[amount],即凑成amount的组合数
        //base case
        dp[0] = 1;  
        for (auto coin:coins)
        {
        for(int n=0;n<dp.size();n++)//自底而上
        {
          
                if((n-coin)<0) continue; //子问题无解，跳过
                dp[n]+=dp[n-coin];
            }
        }
        return dp[amount];
    }
};

[174] 地下城游戏

解题思路

反向DP，为啥用反向？因为要正向更新dp无法更新当前所需最小的生命值。下面是我一开始用的正向DP：

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        //vector<vector<int> >a(n, vector<int>(m, 0))表示的是申请n*m的二维数组
        vector<vector<int>> dp_remian(dungeon.size()+1, vector<int>(dungeon[0].size()+1,0));//记录剩余健康值的二维dp
        vector<vector<int>> dp_k(dungeon.size() + 1, vector<int>(dungeon[0].size() + 1, 0));//记录当前所需的最小健康值k

        //base case
        dp_remian[0][0] = dungeon[0][0]>0? dungeon[0][0]+1:1;//初始位置剩余生命值
        dp_k[0][0] = dungeon[0][0]>0 ?1:abs(dungeon[0][0])+1;//初始位置健康值k

        //遍历完成两个dp表
        for (int row = 0; row < dungeon.size(); row++)
        {
            for (int col = 0; col < dungeon[0].size(); col++)
            {
                if (row == 0 && col == 0) continue;
                if (row== 0 && col>0)
                {
                    dp_remian[row][col] = (dp_remian[row][col - 1] + dungeon[row][col])>0 ? dp_remian[row][col - 1] + dungeon[row][col] : 1;
                    dp_k[row][col] = (dp_remian[row][col - 1] + dungeon[row][col])>0 ? dp_k[row][col - 1] : dp_k[row][col - 1] + abs(dp_remian[row][col - 1] + dungeon[row][col]) + 1;
                }
                else if(row >0 && col==0)
                {
                    dp_remian[row][col] = (dp_remian[row - 1][col] + dungeon[row][col])>0 ? dp_remian[row - 1][col] + dungeon[row][col] : 1;
                    dp_k[row][col] = (dp_remian[row - 1][col] + dungeon[row][col])>0 ? dp_k[row - 1][col] : dp_k[row - 1][col] + abs(dp_remian[row - 1][col] + dungeon[row][col]) + 1;
                }
                else
                {
                    int tempk_left = (dp_remian[row][col - 1] + dungeon[row][col])>0 ? dp_k[row][col - 1] : dp_k[row][col - 1] + abs(dp_remian[row][col - 1] + dungeon[row][col]) + 1;
                    int tempk_up = (dp_remian[row - 1][col] + dungeon[row][col])>0 ? dp_k[row - 1][col] : dp_k[row - 1][col] + abs(dp_remian[row - 1][col] + dungeon[row][col]) + 1;
                    if(tempk_left > tempk_up)  //min
                    {
                        dp_k[row][col] = tempk_up;
                        dp_remian[row][col] = (dp_remian[row - 1][col] + dungeon[row][col])>0 ? dp_remian[row - 1][col] + dungeon[row][col] : 1;
                    }
                    else
                    {
                        dp_k[row][col] = tempk_left;
                        dp_remian[row][col] = (dp_remian[row][col - 1] + dungeon[row][col])>0 ? dp_remian[row][col - 1] + dungeon[row][col] : 1;
                    }
                }
            }
        }
        return dp_k[dungeon.size() - 1][dungeon[0].size()-1];
    }
};

这个方法的话{ {1,-3,3},{0,-2,0},{-3,-3,-3} }这个用例通不过，是因为在第二行第三列选择路线时，根据每一步都选所需初始生命值最小的情况来填dp表的话，很容易忽略从上到下这条全局最优路线，而陷入了局部最优。这样的动态规划是不满足无后效性的。（其实这道题一开始很容易想到倒推，但是由于我DP运用不灵活，尝试用DP时只考虑到了正向）

反向更新dp思路：

确定状态dp[i][j] = k;即dp表中的值表示的是走到当前位置所需的最小初始生命值。换句话说，当我们到达坐标 (i,j)时，如果此时我们的路径和不小于 dp[i][j]，我们就能到达终点。
这样一来，我们就无需担心路径和的问题，只需要关注最小初始值。已知k始终大于等于1，因此dp[i][j]=max(dp[i][j],1)，base case也就是dp[row_length+1][col_length]=dp[row_length][col_length+1] = 1
确定选择如何改变状态:反向走有向左和向上两种，根据两种路线所要扣的血量不同，选择所需最小初始生命值最小的那一步。写出状态转移方程:
dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])−dungeon(i,j),1),即下一个状态为本状态的 $k_1$ 值加上改变量 $\Delta$ 后的 $k_2(min)$ ,且 $k_1 = k_2(min)-\Delta \geq 1$
拿{ {1,-3,3},{0,-2,0},{-3,-3,-3} }情况举例：

1	-3	3
0	-2	0
-3	-3	-3

对应的DP表为：

3	4	1	MAX
6	6	4	MAX
10	7	4	1
MAX	MAX	1	MAX

再拿{ {-2 ,-3,3},{-5,-10,1},{10,30,-5} }情况举例：

-2	-3	3
-5	-10	1
10	30	-5

对应的DP表为：

7	5	2	MAX
6	11	5	MAX
1	1	6	1
MAX	MAX	1	MAX

在网上看到的另一种解读思路：

负数记录，负数的相反数表示从此处走到右下角所需要扣的血量的最小值，即所需的最低初始健康点数-1
更新状态分两步：(我用的是负数进行更新，但从其相反数进行理解)
dungeon[i][j] = dungeon[i][j] + Math.max(dungeon[i + 1][j], dungeon[i][j + 1]);
取下一步的所需要扣的血量的最小值(负数用max)与此处的数值的和
if (dungeon[i][j] > 0) dungeon[i][j] = 0;
所需要扣的血量的最小值最小为零，不可能为负数 (指该处数值的相反数)
总的状态转移方程：dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])+dungeon(i,j),1)

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        //vector<vector<int> >a(n, vector<int>(m, 0))表示的是申请n*m的二维数组
        vector<vector<int>> dp_k(dungeon.size() + 1, vector<int>(dungeon[0].size() + 1, INT_MAX));//记录当前所需的最小健康值k（初始化为最大值）

        //base case
        dp_k[dungeon.size() ][dungeon[0].size() - 1] = 1;//最小需要的健康值
        dp_k[dungeon.size() - 1][dungeon[0].size() ] = 1;

         //根据状态转移方程遍历完成二维dp表，反向
        for (int row = dungeon.size()-1; row >=0; row--)
        {
            for (int col = dungeon[0].size() - 1; col >=0; col--)
            {
                dp_k[row][col] = max(min(dp_k[row+1][col],dp_k[row][col+1])-dungeon[row][col],1);
            }
        }
        return dp_k[0][0];
    }
};

[64] 最小路径和

这道题和上面那道题就比较相似了，但是比较简单，用正向DP即可完成。这道题后面可以试一下用DFS。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        vector<vector<int>> dp(grid.size()+1,vector<int>(grid[0].size()+1,INT_MAX));  
        dp[0][1] = dp[1][0] =0;   
        for(int i = 1; i<=grid.size();i++)
        {
            for(int j = 1;j<=grid[0].size();j++)
            {
                dp[i][j] = grid[i-1][j-1]+min(dp[i-1][j],dp[i][j-1]);
            }
        }    
        return dp[grid.size()][grid[0].size()];
    }
};

小总结一下一般列出状态转移方程可以先画出递归树（状态转移图），或者画出DP表。目前备忘录用的较少，一般回溯+备忘录（记忆）。

未完待续。。。