动态规划--5道题入门（C++力扣）（小细节多）_力扣题目学习c++

动态规划是由递归一步步优化出来的

递归–>记忆化递归–>动态规划

动态规划与其说是一个算法，不如说是一种方法论。该方法论主要致力于将合适的问题拆分成三个子目标——击破：

1.建立状态转移方程
2.缓存并复用以往结果
3.按顺序从小往大算

**总结：
递归到记忆化递归有三步：
1.将递归函数转换为辅助函数，新建全局容器，并在主函数里面初始化大小。

2.在辅助函数中添加if条件语句，考虑当数组容器为-1时的情况。

3.将递归等价关系取得的值记忆到数组容器中去。**

比如：

一、斐波那契额数列（剑指offer10-I）

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1
示例 2：

输入：n = 5
输出：5

1.最常用的解法，递归：

class Solution {
public:
    int fib(int n) {
        //1.结束条件
        if(n<2) return n;
        if(n>(1e9+7))return 1;
        
        //2.找等价函数
        return (fib(n-1)+fib(n-2));   
    }
};
1
2
3
4
5
6
7
8
9
10
11

结果超时，因为一旦要求的n偏大，就会出现大量的重复计算：

2.递归+记忆化：
到达32的时候仍然会超时。按理说应该可以通过1
下面错误的原因在于，只需要一个数组容器用来保存，但是你这样的话每次递归都会创建一个数组容器，导致错误。一定要确保递归的正确性。

class Solution {
public:
    int fib(int n) {
        if(n==0) return 0;
         if(n==1) return 1;
        vector<int>mem(n+1,-1);
        //1.结束条件         
        //mem[0]=0;
        //mem[1]=1;       
        //2.找等价函数  
        if(mem[n]==-1) mem[n]=(fib(n-1)+fib(n-2))%1000000007; 
        return mem[n] ;  
    }   
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

修改后成功了！！！！！！！！！！！！！！！！！！！！！！！！！！！！

class Solution {
public:
	 int fib(int n) {
	 mem=vector(n+1,-1);
	 return fibs(n);
	 }
private:
	vector<int>mem;
    int fibs(int n) {
        if(n<2) return n;
        if(mem[n]==-1) mem[n]=(fibs(n-1)+fibs(n-2))%1000000007; 
        return mem[n] ;  
    }   
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

**总结：
递归到记忆化递归有三步：
1.将递归函数转换为辅助函数，新建全局容器，并在主函数里面初始化大小。

2.在辅助函数中添加if条件语句，考虑当数组容器为-1时的情况。

3.将递归等价关系取得的值记忆到数组容器中去，最后返回容器。

分开的原因暂时未知！

3.动态规划

自下而上的解决问题

class Solution {
public:
    int fib(int n) {
        if(n==0) return 0;
        vector<int>mem(n+1,-1);
        //1.结束条件         
        mem[0]=0;
        mem[1]=1;
        
        //注意for循环里面时三个mem
       for (int i = 2; i <= n; i++){
           mem[i]=(mem[i-1]+mem[i-2])%1000000007; 
       } 
        return mem[n] ;  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

记忆化递归到动态规划总结：
1.又合并只有一个函数，对数组容器原地进行创建并初始化。

2.把递归的结束条件转换为数组容器的值。

3.利用遍历和数组容器中已存在的值，找到数组容器中的等价关系(注意等价关系的容器数组下标不再含有n)，最后返回所需要的容器值。

注意：
1.一定要搞清楚数组容器中保存的是什么！
2.数组容器的等价关系，一定要搞清楚谁利用谁，才能确定是从前往后还是从后往前遍历！

4.优化空间之后

class Solution {
    public int fib(int n) {
        if(n==0)return 0;
        if(n==1)return 1;
 
        int a=0,b=1;
        for(int i=2;i<=n;i++){
            int x = (a+b)%1000000007;
            a=b;
            b=x;
        }
        return b;
    }
}

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

二、青蛙跳台问题(剑指offer10-II)

1.递归：

class Solution {
public:
    int numWays(int n) {
        if(n==0)return 1;
        if(n==1)return 1;
        return numWays(n-1)+numWays(n-2);
    }
};
1
2
3
4
5
6
7
8

2.递归+记忆优化

因为重复太多，所以需要记忆。

递归到记忆化递归有三步：

1.将递归函数转换为辅助函数，新建全局容器，并在主函数里面初始化大小。

2.在辅助函数中添加if条件语句，考虑当数组容器为-1时的情况。

3.将递归等价关系取得的值记忆到数组容器中去(注意等价关系的容器数组下标不再含有n)，最后返回容器。

class Solution {
public:
   
    int numWays(int n) {
       mem=vector(n+1,-1);
       return tiaotai(n);
    }
private:
    vector<int>mem;
    int tiaotai(int n){
         if(n==0)return 1;
        if(n==1)return 1;
        if(mem[n]==-1)
        mem[n]=(tiaotai(n-1)+tiaotai(n-2))%1000000007;
        return mem[n];
    }

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

记忆化递归到动态规划总结：
1.又合并只有一个函数，对数组容器原地进行创建并初始化。

2.把递归的结束条件转换为数组容器的值。

3.利用遍历和数组容器中已存在的值，找到数组容器中的等价关系(注意等价关系的容器数组下标不再含有n)，最后返回所需要的容器值。
一定要搞清楚数组中保存的是什么!!!

3.动态规划

直接这么写输入0总是报错

class Solution {
public:
    int numWays(int n) {
    vector<int>mem(n+1,-1);
      mem[0]=1;
      mem[1]=1;
      for(int i=2;i<=n;i++){
          mem[i]=(mem[i-1]+mem[i-2])%1000000007;
      }
      return mem[n];
    } 
};
1
2
3
4
5
6
7
8
9
10
11
12

直接把1储存到所有的数组元素中反而正确

class Solution {
public:
    int numWays(int n) {
     //动态规划4行解决
        //声明n+1大小的vector，+1是要存储0至n共n+1个数据。
         vector<int> v(n + 1, 1);   
         for(int i = 2; i <= n; i++)
            v[i] = (v[i - 1] + v[i - 2]) % 1000000007;//注意别忘记取余
           return v[0];//直接返回最后一个数，即最终结果


    } 
};
1
2
3
4
5
6
7
8
9
10
11
12
13

4.空间优化：

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

或者这种

class Solution {
public:
    int numWays(int n) {

        //创建一个数组，
        //数组大小尽量大，因为它是可以取的n的最大范围
        int ans[500]={1,1};

        //把每一种台阶数对应的跳法总数存到对应数组中
        for(int i=2;i<=n;i++) ans[i]=(ans[i-1]+ans[i-2])%(int(1e9+7));
        //返回所取的台阶对应跳法数
        return ans[n];

    }
};

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

三、 整数拆分（Leetcode343）

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

1.普通递归（超时）

class Solution {
private:
        
        int Max(int a, int b, int c){
            return max(a,max(b,c));
        }
        int _integerBreak(int n){
            //结束条件
            if(n==1)return 1;
            //寻找等价关系
            int res=-1;
            for(int i=1; i<n; i++){
                res=Max(res,i*(n-i), i*_integerBreak(n-i));
            }
            return res;
        }
public:
    int integerBreak(int n) {
      //vector<int>(n+1,-1);
      return   _integerBreak(n);
    }

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

2.记忆化递归

class Solution {
private:
         vector<int>mem;
        int Max(int a, int b, int c){
            return max(a,max(b,c));
        }
        int _integerBreak(int n){
            //结束条件
            if(n==1)return 1;
            //寻找等价关系
            if(mem[n]!=-1)return mem[n];

            int res=-1;
            for(int i=1; i<n; i++){
                res=Max(res,i*(n-i), i*_integerBreak(n-i));
            }
            mem[n]=res;
            return res;
        }
public:
    int integerBreak(int n) {
        assert(n>=2);
      mem = vector<int>(n+1,-1);
      return   _integerBreak(n);
    }

};
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

3.动态规划

记忆化递归到动态规划总结：
1.又合并只有一个函数，对数组容器原地进行创建并初始化。

2.把递归的结束条件转换为数组容器的值。

3.利用遍历和数组容器中已存在的值，找到数组容器中的等价关系(注意等价关系的容器数组下标不再含有n)，最后返回所需要的容器值。

class Solution {
private:
         
        int Max(int a, int b, int c){
            return max(a,max(b,c));
        }               
public:
    int integerBreak(int n) {
        assert(n>=2);
      vector<int>mem(n+1,-1);
      mem[1]=1;
      
      int res=-1;
      for(int i=2; i<=n; i++){
          for(int j=1;j<i;j++) {
              res=Max(res,j*(i-j), j*mem[i-j]);
              mem[i]=res;
          }
        }

      return mem[n];
    }

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

四、三角形求和(Leetcode120)

题意：
给定三角形，每次只能移动到下一行中的相邻结点，求从顶点到底边的最小路径和。

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
相邻结点：与(i, j) 点相邻的结点为 (i + 1, j) 和 (i + 1, j + 1)。

分析：
若定义 f(i, j)f(i,j) 为 (i, j)(i,j) 点到底边的最小路径和，则易知递归求解式为:

f(i, j) = min(f(i + 1, j), f(i + 1, j + 1)) + triangle[i][j]

由此，我们将任一点到底边的最小路径和，转化成了与该点相邻两点到底边的最小路径和中的较小值，再加上该点本身的值。这样本题的 递归解法（解法一） 就完成了。

1.纯递归的错误方法，因为会超时：

class Solution {
    private:
        int dfp(vector<vector<int>>& triangle,int i, int j){

            //结束条件
            //i,j代表从哪个点一直向下的路径之和
            //下面的条件是i已经超过最底端，所以路径和返回0
            if(i==triangle.size())return 0;
           
            //等价关系
            return min(dfp(triangle,i+1,j),dfp(triangle,i+1,j+1))+triangle[i][j];
        }      
public:
    int minimumTotal(vector<vector<int>>& triangle) { 
        int n = triangle.size();
        //对辅助容器的初始化，初始化后二维数组的空间值自动赋值为0
        
        return   dfp(triangle,0,0);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

暴力搜索会有大量的重复计算，导致 超时，因此在 解法二 中结合记忆化数组进行优化。

2.递归加记忆化的方法：

class Solution {
    //递归的记忆化辅助
    vector<vector<int>>mem;
    private:
        int dfp(vector<vector<int>>& triangle,int i, int j){

            //结束条件
            //i,j代表从哪个点一直向下的路径之和
            //下面的条件是i已经超过最底端，所以路径和返回0
            if(i==triangle.size())return 0;
            if (mem[i][j] != 0) {
             return mem[i][j];
            }
            //等价关系
            return mem[i][j]=min(dfp(triangle,i+1,j),dfp(triangle,i+1,j+1))+triangle[i][j];
        }      
public:
    int minimumTotal(vector<vector<int>>& triangle) { 
        int n = triangle.size();
        //对辅助容器的初始化，初始化后二维数组的空间值自动赋值为0
        mem=vector<vector<int> >(n, vector<int>(n));
        return   dfp(triangle,0,0);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.动态优化
定义二维 dp 数组，将解法二中「自顶向下的递归」改为「自底向上的递推」

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) { 
        int n = triangle.size();
        //对辅助容器的初始化，初始化后二维数组的空间值自动赋值为0
        vector<vector<int>>dp(n+1, vector<int>(n+1));
        //把每一个位置从底到该处的最小路径之和都算出来
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
            }
        }
        return   dp[0][0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.空间优化
3的解法把三角形每一个位置从下到上的路径之和都搞了出来，其实没必要，因为我们只要求从下到最顶点的路径之和，所以只需要用一行数组保存前一层的路径之和让后一层用就可以，这样就更加节省空间。

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) { 
        int n = triangle.size();
       
        vector<int>dp(n+1);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
            }
        }
        return   dp[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

五、求左上到右下的最小路径和(Leetcode64)

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

1.路径规划的方法
最主要是的搞清楚往临时容器中放的是什么，一次性循环放和分开放都可以！

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        if(m==0 && n==0)return 0;
        //对辅助容器的初始化，初始化后二维数组的空间值自动赋值为0
        vector<vector<int>>dp(m, vector<int>(n));
        //int dp[m][n]; //容器或数组两个都可以
        dp[0][0]=grid[0][0];
          // 第1行 计算

        //第一行初始化
        //注意后面是加grid[][]!
        for(int i=1; i<n;i++){
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        //第一列的初始化
        for(int j=1; j<m; j++){
            dp[j][0]=dp[j-1][0]+grid[j][0];
        }
        
        //把不是第一行第一列位置从起始处到该位置的和算出来初始化
        for (int i = 1; i <m; i++) {
            for (int j = 1; j <n; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) +grid[i][j];
            }
        }
        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

2.进行空间优化
想不到想不到
不知道这种二维变一维的空间优化大佬们是怎样想到的，反正我想不到！

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


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

个人在大学时习惯于根据决策推进方向可化分为向前和向后两类。

官方视频讲解针对样例给出了由后向前推进的解析，并给出了简化dp数组为一维的方法。本文以一维dp数组为解题基础通过向前推进决策的方法给与此题解答。

本文将解决此题的方法概括为“数组降维，逐行更新”
一.数组降维
开辟一个长度等于原二维grid数组列长(设为cols)的一维数组(vector dp(cols, grid[0][0]))
动态规划问题又可以理解为多段决策最优问题，那么dp[i]表示在前面i-1步已做出最优决策的前提下第i步做出的决策，并且使得前i步得到的收益最大(本题中指路径最短)。
值得提出的是，虽然题目中规定了每个点只能向下或者向右移动，但对于第一行的任意点来说，没有上一行的点会向下移动到该位置。由此对于第一行建立以下等式
dp[i] = grid[0][i] + dp[i - 1]; (1)
以题干给出的示例为例:遍历第一行以后
dp数组的值为{1, 4, 5}

二.逐行更新
设想我们从第二行开始,每一行的每一个点都可以由上边的点向下移动经过。
对于第i行第j列的点(i > 1)逐行遍历至该点时，有两种情况
(1)对于每行的第一个点只有他上边的点向下移动才可以经过该点
(2)剩下的点都可以由他上边的点向下移动或左边的点向右移动到达
对于第一类点，我们遍历到新一行时，由于该点只能由其他点向下移动到达我们就可以根据前一行的dp[0]来更新该点的决策值
dp[0] += grid[i][0] (2)
对于第二类点，我们可以得到如下等式
dp[j] = grid[i][j] + min(dp[j-1],dp[j])
等式右边dp[j]代表当前点上一行对应位置点的决策收益值
dp[j-1]代表当前位置左侧点的决策收益值。

大佬详解链接：动态规划的优化

其他习题：

另外还有力扣的279题，91题，64题，63题。 还有213题，337题，309题。