动态规划入门笔记(九章算法)

---

类型一：最值型

动态规划通常使用四个步骤来解答：

1、确定状态

2、转移方程

3、初始条件和边界情况

4、计算顺序

[图片上传中...(image.png-b17f36-1580630141799-0)]

递归的解法：

#include <iostream>
#include <cmath> 

using namespace std;

int f(int x){
    if(x==0){ return 0;}
    int res = 1000000000;  //无穷大
    
    if(x>=2){
        res = min(fun(x-2) + 1,res);
    }
    if(x>=5){
        res = min(f(x-5) + 1,res);
    }
    if(x>=7){
        res = min(f(x-7) + 1,res);
    }

    return res;
}

int main()
{   

    cout<<f(27);
    
    return 0;
}

由上图可以看出，f(20)计算了三次，f(15)计算了两次。如果让求的
递归数值比较大，就会产生很多重复的计算。

边界情况就是不要让数组越界

计算顺序大多数情况都是从小到大，二维的话就是从上到下，从左到右。

动态规划解法：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {

        //初始化状态数组
        vector<int> f(amount+1);
        int coin_num = coins.size();

        //初始条件
        f[0] = 0;
        int i,j;

        //从小到大计算每个值的值，便于递归使使用，返回最后一个需要的值，即f(amount)的值
        for(int i = 1;i<=amount;i++){
            //刚开始初始化为无穷大
            f[i] = INT_MAX;

            //计算“最后一枚”：f[i] = min(f[i-coin[0]] + 1,....,f[i-coin[n-1] + 1])
            for(int j=0;j<coin_num;j++){
                //保证要计算的值必须大于硬币的面额 && 需要的硬币的个数不能为正无穷,否则加1后溢出(防溢出)
                if(i>=coins[j] && f[i - coins[j]] != INT_MAX){
                    f[i] = min(f[i - coins[j]] + 1,f[i]);
                }
            }
        }

        if(f[amount] == INT_MAX){
            f[amount] = -1;
        }

        return f[amount];        
    }
};

---

类型二：计数型

• 之所以可以使用X+Y，是因为机器人只能向右或向下走，满足“不重复、无遗漏”条件。

• 为什么把原文问题“走到(m-1,n-1)”变成“走到(m-2,n-1)和(m-1,n-2)”就代表分解成了子问题？

  
  
  

  由上图可以看出，矩阵是变小了。

class Solution {
public:
    int uniquePaths(int m, int n) {

        //开辟二维数组保存状态:因为最后为(m-1,n-1)，所以数组大小为m*n，不用再行列加1
        int f [m][n];

        for(int i=0; i<m; i++){              //从上到下
            for(int j=0; j<n; j++){
                if(i==0 || j==0){            //从左到右
                    //出口:边界条件
                    f[i][j] = 1;
                }
                else{
                    //更新(i,j)位置的状态:可以使用加法来分别表示两个方向的更新（上和左）
                    f[i][j] = f[i-1][j] + f[i][j-1];
                }
            }
        }

        return f[m-1][n-1];
        
    }
};

• 注意：确定顺序为从上到下，从左到右的根本原理是利用前面的计算结果。

---

类型三：可行性型（是否存在型）

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        //初始化状态数组
        int n = nums.size();
        bool f[n];

        //初始化初始变量    
        f[0] = true;

        for(int i = 1; i<n; i++){
            f[i] = false;
            for(int j = 0; j<i; j++){                
                if(f[j] && (nums[j] + j >= i)){
                    f[i] = true;
                }
            }
        }

        return f[n-1];
    }
};