算法刷题-动态规划-1

不同路径

//机器人不同的路径进入到指定的地点
public static int uniquepath(int m, int n) {
    if (m <= 0 || n <= 0)
    {
        return 0;
    }
    int[][] dp = new int[m][n];//初始化
   
    //如果只有i，j中有一个为0，那么机器人行走的方向只能有一种方式
    for (int i = 0; i < m; i++)
    {
        dp[i][0] = 1;
    }
    for (itn i = 0; i < n; i++)  
    {
        dp[0][i] = 1;  
    }
    //推导出dp[m-1][n-1]，因为定义dp[i][j]就是表示的是在[i][j]点  
    //不同的路径的数目  
    for (itn i = 1; i < m; i++)    
    {
        for (int j = 1; j < n; j++)    
        {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];    
        }
    }
    return dp[m - 1][n - 1];    

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

不同路径||

![在这里插入图片描述]（https://img-blog.csdnimg.cn/55c59dbc1da64e20aed014ff76118002.png）

方法一：

大佬讲解

class Solution {
public:
    /**
     * 1. 确定dp数组下标含义 dp[i][j] 从(0,0)到(i,j)可能的路径种类;
     * 2. 递推公式 dp[i][j] = dp[i-1][j] + dp[i][j-1] 但是需要加限制条件就是没有障碍物的时候
     *    if(obstacleGrid[i][j] == 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];
     * 3. 初始化 当obstacleGrid[i][j] == 0时，dp[i][0]=1 dp[0][i]=1 初始化横竖就可;
     * 4. 遍历顺序 一行一行遍历;
     * 5. 推导结果;
     */
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        /* 计算数组大小 */
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        /* 定义dp数组 */
        vector<vector<int>> dp(m,vector<int>(n,0));
        /* 初始化dp数组 */
        for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++)
            dp[i][0] = 1; 
        for(int i = 0; i < n && obstacleGrid[0][i] == 0; i++)   
            dp[0][i] = 1;      
        /* 一行一行遍历 */     
        for(int i = 1; i < m; i++) {     
            for(int j = 1; j < n; j++) {     
                /* 去除障碍物 */     
                if(obstacleGrid[i][j] == 1) continue;     
                
                dp[i][j] = dp[i-1][j] + dp[i][j-1];     
            }
        }
        return dp[m-1][n-1];     
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

方法二

多加一行和一列的虚拟节点，防止出现越界的情况，
把它们初始化成0，但是要保证第一个节点初始化成1.
dp[0][1] = 1;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][1] = 1;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(obstacleGrid[i - 1][j - 1] == 1) continue;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第N个泰波那契数

1

递归写法

1。先确定函数的一定是什么dp[ i ] 表示：第 i 个泰波那契数
2。题目中的关系代数是 dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] + dp[ i - 3。边界是T(0)=0,T(1)=1,T(2)=1T(0)=0, T(1)=1,
4。初始化为dp[ 0 ] = 0，dp[ 1 ] = 1，dp[ 2 ] = 1

class Solution {
public:
    int tribonacci(int n) {
        vector<int> dp(n + 1);

        if (n == 0) 
        {
            return 0;   
        }
        if (n <= 2)   
        {
            return 1;   
        }
        dp[0] = 0, dp[1] = 1, dp[2] = 1;   

        for (int i = 3; i <= n; i++) {   
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];   
        }
        return dp[n];   
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

滚动数组

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {  
            return 1;  
        }

        int p = 0, q = 0, r = 1, s = 1;  

        for (int i = 3; i <= n; ++i) {  
            p = q;  
            q = r;  
            r = s;  
            s = p + q + r;  
        }
        return s;  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三步问题

这就是老油条的步骤了，
先确定自己定义的函数，然后找出关系式，然后确定初始值

递归操作

class Solution {  
public:  
    int waysToStep(int n) {  
        vector dp(n + 1);  
        const int MOD = 1e9 + 7;  
        //边界问题    
        if (n == 1 || n == 2) return n;    
        if (n == 3) return 4;    

        //初始化定义    
        dp[1] = 1, dp[2] = 2, dp[3] = 4;    

        for (int i = 4; i <= n; i++) {   
            dp[i] = ((dp[i - 3] + dp[i - 2]) % MOD + dp[i - 1]) % MOD;   
        }
        return dp[n];   
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

滚动数组

class Solution {    
public:    
    int waysToStep(int n) {     
        int a=1,b=2,c=4,i;     
        for(i=2;i<=n;i++){     
            long long t=(a+b)%1000000007;     
            t=(t+c)%1000000007;     
            a=b;     
            b=c;     
            c=t;     
        }
        return a;     
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

使用最小画法爬楼梯

题目要求的是到达第n级台阶楼层顶部的最小花费，可以用动态规划来解，下面一步一步来讲怎样确定状态空间、怎样给出状态转移方程。

递归

1. 大佬讲解

2. 最近的一步有两种情况，

3. 从 dp[ i - 1 ] 走一步过来，支付cost[ i - 1 ] 的费用； 1. 从 dp[ i - 1 ] 走一步过来，支付cost[ i - 1 ] 的费用;

4. 从 dp[ i - 2 ] 走两步过来，支付cost[ i - 2 ] 的费用。
   而 dp[ i ] 就是到达 i 位置的最小花费，
   那我们就能得出状态转移方程：
   dp [ i ] = min( dp[ i - 1 ] + cost[ i - 1 ]，dp[ i - 2 ] + cost[ i - 2 ] )

class Solution {  
public:  
    int minCostClimbingStairs(vector<int>& cost) {  

        int n = cost.size();  

        // 创建dp表，这样初始化默认填充的是 0   
        vector<int> dp(n + 1);  

       
        for (int i = 2; i <= n; i++) {  
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);  
        }

        return dp[n];  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解码方法

方法一

动态规划的使用：
1。确立dp 数组的定义，代表的是 dp[i] 位置代表的是第i个位置时候解码方法的总数。
2。找关系代数=

1. s[ i ] 单独解码，如果是单独解码，当 s[ i ] 的值是 1~9 的时候可以自己解码，
   自己解码的方案数就是 dp[ i - 1 ]，如果 s[ i ] 的值是 0，那方案数就是0，整体解码失败，

2. s[ i ] 和 s[ i - 1 ] 一起解码，当 s[ i - 1 ] * 10 + s[ i ] 的值是 10~26 的时候就可以解码，
   而解码数就是 dp[ i - 2 ]，如果解码失败，不在这个区间内，那方案数就也是0。
   3。初始化dp数组，
   初始化 dp[ 0 ] 和 dp[ 1 ] 位置，
   dp[ 0 ] 位置，如果s[ 0 ] 解码成功就是1，不成功就是0
   dp[ 1 ] 位置，如果 dp[ 1 ] 能自己解码，就 + 1，如果能跟 dp[ 0 ] 一起解码，就再 + 1，
   如果dp[ 1 ] 两种情况都不能解码，就是0。（所以可能是0, 1, 2）

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(size);

        dp[0] = s[0] != '0';
        if (size == 1) return dp[0];

        if (s[0] != '0' && s[1] != '0') dp[1]++;
        int t = (s[0] - '0') * 10 + (s[1] - '0');

        if (t >= 10 && t <= 26) dp[1]++;

        for (int i = 2; i < size; i++) {
            if (s[i] != '0') dp[i] += dp[i - 1]; 

            t = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if (t >= 10 && t <= 26) dp[i] += dp[i - 2]; //一起解码
        }
        return dp[n - 1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二：（大佬讲解）

class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0') return 0;
        int n = s.size();
        vector<int> dp(n + 1, 1);
        //dp[0]表示s[-1]的状态， dp[1] 表示 s[0]的状态
        //dp[i] 表示 s[i-1]的状态
        for (int i = 2; i <= n; i++) {
            if (s[i - 1] == '0') {
                if (s[i - 2] == '1' || s[i - 2] == '2')//唯一译码，不增加情况
                    dp[i] = dp[i - 2]; 
                else//这里要好好理解一下，比如给定340, 输出可行的编码数为0， 因为0和40都无法转换  
                    return 0;  
            }
            else if (s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] >= '1' && s[i - 1] <= '6')


                dp[i] = dp[i - 1] + dp[i - 2];  
            else//当上述条件都不满足，维持上一个状态  
                dp[i] = dp[i - 1];  
        }
        //for(auto c:dp) cout << c << ",";  
        return dp[n];//返回dp[n] 即最后 s[n-1] 的状态  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26