动态规划入门专题（超详细！！！）

题目特点

1.计数

• 有多少种方式走到右下角
• 有多少种方法选出k个数使得和为sum

2.求最值

• 从左上角走到右下角路径的最大数字和
• 最长上升子序列长度

3.求存在性

• 取石子游戏，先手是否必胜
• 能不能选出k个数使得和为sum

题目特点

组成部分一：确定状态

简单来说，解动态规划的时候需要开一个数组，数组的每个元素f[i]或f[i][j]代表什么（类似于解数学题中，X、Y、Z 代表什么）

确定状态需要两个意识：
最后一步（最优策略中的最后一个决策）
子问题（问题相同，但规模变小）

组成部分二：转移方程

组成部分三：初始条件和边界情况

其中初始条件往往是用转移方程无法求得出结果，需要人为定义。

组成部分四：计算顺序

大多数情况：从小到大（一维）从上到下从左到右（二维）

例题

例题一（LintCode 669:Coin Change）（求最值型）

你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多
买一本书需要27元
如何用最少的硬币组合正好付清，不需要对方找钱

分析

1.确定状态
此时最后一枚硬币为最后一步（即去掉这一步后，前面的K-1枚硬币依然为最优策略）

所以此时问题可以从原来的“最少用多少枚硬币拼出27”转化为一个子问题，而且规模更小“最少用多少枚硬币可以拼出27-ak”。

为简化定义，设状态f(x) = 最少用多少枚硬币拼出x

由于ak的取值情况只可能是2,5或者7
故如果ak为2，则f(27) = f(27-2) + 1(加上最后这一枚硬币2)
如果ak为2，则f(27) = f(27-5) + 1(加上最后这一枚硬币5)
如果ak为2，则f(27) = f(27-7) + 1(加上最后这一枚硬币7)

需要求最少的硬币数，所以：
f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}

2.转移方程
转移方程形式：f[x] = min{f[27-2]+1, f[27-5]+1, f[27-7]+1}

3.初始条件和边界情况
若不能拼出Y，则定义f[Y] = +∞
eg：f[1] = min{f[-1]+1, f[-4]+1, f[-6]+1} = +∞ （表示拼不出来1）

初始条件：f[0] = 0

4.计算顺序
计算f[1],f[2],f[3],…,f[27]
当我们计算到f[x]时，f[x-2],f[x-5],f[x-7]都已经得到结果了

代码部分

class Solution {
public:
    /**
     * @param coins: a list of integer
     * @param amount: a total amount of money amount
     * @return: the fewest number of coins that you need to make up
     */
    const int MAX_VALUE = 0x3f3f3f3f; //无穷大
    int coinChange(vector<int> &coins, int amount) {
        // write your code here
        int result[amount + 1]; //+1表示我这里需要用到 amount
        result[0] = 0; //初始条件
        for (int i = 1; i <= amount; i++)
        {
            result[i] = MAX_VALUE; //先初始化为最大值，这里是考虑到了不存在硬币的情况
            for (int j = 0; j < coins.size(); j++)
            {
                if (i >= coins[j] && result[i - coins[j]] != MAX_VALUE)
                {
                    result[i] = min(result[i - coins[j]] + 1, result[i]); //就是那条公式的一个转换
                }
            }
        }
        if (result[amount] == MAX_VALUE)
            return -1;
        else
            return result[amount];
    }
};

例题二（LintCode 114:Unique Paths）（计数型）

给定m行n列的网格，有一个机器人从左上角（0,0）出发，每一步可以向下或者向右走一步
问有多少种不同的方式走到右下角

分析

1.确定状态
最后一步：无论机器人用何种方式到达右下角，总有最后挪动一步：向右或向下
右下角坐标设为（m-1，n-1）
则前一步机器人一定在（m-2，n-1）或（m-1，n-2）

子问题：
原题“求有多少种方式从左上角走到（m-1，n-1）”
子问题“求有多少种方式从左上角走到（m-2，n-1）和（m-1，n-2）”

状态：设f[i][j]为机器人有多少种方式从左上角走到（i，j）（有多少变量就开几维数组）

2.转移方程
对于任意一个格子（i，j）
f[i][j]：有多少种方式从左上角走到（i，j）
f[i][j] = f[i-1][j] + f[i][j-1]

3.初始条件和边界情况
初始条件：f[0][0] = 1 //机器人只有一种方式到左上角

边界情况：i=0或j=0，则前一步只能由一个方向过来—>f[i][j] = 1

4.计算顺序
f[0][0] = 1
计算第0行：f[0][0]，f[0][1]，f[0][2]，…，f[0][n-1]
计算第1行：f[1][0]，f[1][1]，f[1][2]，…，f[1][n-1]
…
计算第m-1行：f[m-1][0]，f[m-1][1]，f[m-1][2]，…，f[m-1][n-1]
答案：f[m-1][n-1]
时间复杂度度（计算步数）：O（mn）
空间复杂度（数组大小）：O（mn）

代码部分

class Solution {
public:
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    int uniquePaths(int m, int n) {
        // write your code here
        int f[m][n];
        for(int i=0;i<m;i++){ // row : top to bottom
            for(int j=0;j<n;j++){ // column: left to right
                if(i == 0 || j == 0)
                    f[i][j] = 1;
                else
                    f[i][j] = f[i-1][j] + f[i][j-1];
            }
        }
        return f[m-1][n-1];
    }
};

例题三（LintCode 116:Jump Game）（存在性型）

有n块石头分别在x轴的0,1，…，n-1位置
一只青蛙在石头0，想跳到石头n-1
如果青蛙在第i块石头上，它最多可以向右跳距离ai
问青蛙能否跳到石头n-1

例子：
输入：a = [2, 3, 1, 1, 4]
输出：True
输入：a = [3, 2, 1, 0, 4]
输出：False

1.确定状态
最后一步：如果青蛙能跳到最后一块石头n-1，我们考虑它跳的最后一步
这一步是从石头i跳过来，i < n-1
这需要两个条件同时满足：
a.青蛙可以跳到石头i
b.最后一步不超过最大跳跃距离：n-1-i <= ai
子问题：
原问题“求青蛙能不能跳到石头n-1”
子问题“求青蛙能不能跳到石头i(i < n-1)”

状态：设f[j]表示青蛙能不能跳到石头j

2.转移方程
设f[j]表示青蛙能不能跳到石头j
f[j] = OR(0<= i <=j-1)(f[i] AND i + a[i] >= j)
其中
(0<= i <=j-1)表示枚举上一个跳到石头i
f[i]表示青蛙能不能跳到石头i
i + a[i] >= j 表示最后一步不能超过ai
OR表示只要有一个i满足即返回true，否则返回false

3.初始条件和边界情况
初始条件：f[0] = True，因为青蛙一开始就在石头0
边界情况：不会越界

4.计算顺序
计算f[0], f[1], f[2], … , f[n-1]
答案是f[n-1]

时间复杂度：O（N^2） 空间复杂度（数组大学）：O（N）

代码部分

class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    bool canJump(vector<int> &A) {
        // write your code here
        int n = A.size();
        bool f[n];
        f[0] = true; // initialization
        
        for(int j=1;j<n;j++){
            f[j] = false;
            // previous stone i
            // last jump is from i to j
            for(int i=0;i<j;i++){
                if(f[i] && i + A[i] >= j){
                    f[j] = true;
                    break;
                }
            }
        }
        
        return f[n-1];
    }
};

总结

确定状态

研究最优策略的最后一步
化为子问题

转移方程

根据子问题定义直接得到

初始条件和边界情况

细心、考虑周全

计算顺序

利用之前的结果

本文地址：https://blog.csdn.net/qq_43662165/article/details/108566880