动 态 规 划

1 斐波拉切数列

现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

问题出处，兔子繁殖问题：

1.1 递归

//递归，，，，斐波那契数列公式为：f[n] = f[n-1] + f[n-2], 初始值f[0]=0, f[1]=1，f[2]=1,

int f1(int n) {
	if (n < 2) return n;
	return f1(n - 1) + f1(n - 2);
}
1
2
3
4

//递归,时间复杂度：O(2^n) 空间复杂度O(n)

int f2(int n) {
	return n < 2 ? n : f2(n - 1) + f2(n - 2);
}
1
2
3

优点，代码简单好写，缺点：慢；

1.2 数组记忆，避免重复计算

通过图会发现，，存在很多重复计算，因为为了改进，就把计算过的保存下来。 那么用什么保存呢？一般会想到map， 但是此处不用牛刀，此处用数组就好了。

int f3(int n) {
int f[50]{0};
        if (n <= 2) return 1;
        if (f[n] > 0) return f[n];
        return f[n] = (Fibonacci(n-1)+Fibonacci(n-2));
}
1
2
3
4
5
6

时间复杂度：O（n）， 没有重复的计算 空间复杂度：O（n）和递归栈的空间

1.3 动态规划

虽然方法二可以解决此题了，但是如果想让空间继续优化，那就用动态规划，优化掉递归栈空间。 方法二是从上往下递归的然后再从下往上回溯的，最后回溯的时候来合并子树从而求得答案。 那么动态规划不同的是，不用递归的过程，直接从子树求得答案。过程是从下往上。

  int Fibonacci(int n) {
        int dp[50]{0};
        dp[1] = 1, dp[2] =1;
        for (int i = 3 ; i <= n ; i ++) dp[i] = dp[i-1]+dp[i-2];
        return dp[n];
    }
1
2
3
4
5
6

时间复杂度：O(n) 空间复杂度：O(n) ###继续优化 发现计算f[5]的时候只用到了f[4]和f[3], 没有用到f[2]…f[0],所以保存f[2]…f[0]是浪费了空间。 只需要用3个变量即可。

1.4 动态规划 优化（去掉数组保存，只用3个变量）

int Fibonacci(int n) {
        int a = 1 , b = 1 , c = 1;
        for (int i = 3 ; i <= n ; i ++) {
            c = a+b , a = b , b = c;
        }
        return c;
    }
1
2
3
4
5
6
7

时间复杂度：O（n） 空间复杂度：O（1） 完美！

2 动态规划 理论上

动态规划

举例 fibonacci

递归

记忆化

通过上图会发现，存在很多重复计算。
改进dp[n]已经被计算过，就不再计算，，否则计算；

if(!dp[n])
      dp[n] = Fibonacci(n-1) + Fibonacci(n-2);
1
2

那么，结果是，所有的状态只会计算一次

 int Fibonacci(int n) {
           int dp[50]{0};
           if (n<=2) return 1;
           else if(!dp[n])
                dp[n] = Fibonacci(n-1) + Fibonacci(n-2);
           
           return dp[n];
    }
1
2
3
4
5
6
7
8

递归+ 记忆化 优化到时间复杂度为 O(n);

递归 + 记忆化 = 递推

递归：自上而下；
动态规划；自下而上（终点->起点）

int Fibonacci(int n) {
        int dp[50]{0};
        dp[1] = 1, dp[2] =1;
        for (int i = 3 ; i <= n ; i ++) dp[i] = dp[i-1]+dp[i-2];
        return dp[n];
    }
1
2
3
4
5
6

3 动态规划 理论下

3.1 从起点走到终点，有多少种走法（无障碍物）

描述
一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

备注：m和n小于等于100,并保证计算结果在int范围内

数据范围：0 < n,m ≤100，保证计算结果在32位整型范围内
要求：空间复杂度 O(nm)，时间复杂度 O(nm)
进阶：空间复杂度 O(1)，时间复杂度 O(min(n,m))

3.1 递归 1

思路：

首先我们在左上角第一个格子的时候，有两种行走方式：
如果向右走，相当于后面在一个(n−1)∗m的矩阵中查找从左上角到右下角的不同路径数；
而如果向下走，相当于后面在一个n∗(m−1)的矩阵中查找从左上角到右下角不同的路径数。
而(n−1)∗m的矩阵与n∗(m−1)的矩阵都是n∗m矩阵的子问题，因此可以使用递归。

具体做法：

step 1：（终止条件） 当矩阵变长n减少到1的时候，很明显只能往下走，没有别的选择了，只有1条路径；同理m减少到1时也是如此。因此此时返回数量为1.
step 2：（返回值） 对于每一级都将其两个子问题返回的结果相加返回给上一级。
step 3：（本级任务） 每一级都有向下或者向右两种路径选择，分别进入相应分支的子问题。

int uniquePaths(int m, int n) {
       //地图宽或高为1时，只有一种走法；
        //if(m == 1 || n == 1 ) return 1;
       // return uniquePaths(m-1,n) + uniquePaths(m,n-1);
}
1
2
3
4
5

3.2 动态规划

思路：

如果我们此时就在右下角的格子，那么能够到达该格子的路径只能是它的上方和它的左方两个格子，

因此从左上角到右下角的路径数应该是从左上角到它的左边格子和上边格子的路径数之和，因此可以动态规划。

具体做法：

step 1：用dp[i][j]表示大小为i∗ji*ji∗j的矩阵的路径数量，下标从1开始。
step 2：（初始条件） 当i或者j为1的时候，代表矩阵只有一行或者一列，因此只有一种路径。
step 3：（转移方程） 每个格子的路径数只会来自它左边的格子数和上边的格子数，因此状态转移为dp[i][j]=dp[i−1][j]+dp[i][j−1]。

int uniquePaths(int m, int n) {
        //path[i][j]表示大小为i*j的矩阵的路径数量
       vector<vector<int>> path(m + 1,vector<int>(n + 1,0));//设置大小为m+1,n+1，方便下标从一开始，(0,0)地址空间舍弃
       
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                if(i == 1 || j == 1 ) {//只有1行或1列的时候，只有一种路径
                    path[i][j] = 1 ;
                    continue;
                }   
                path[i][j]  = path[i-1][j] + path[i][j-1];
            }
        return path[m][n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.3 方法三：数学公式 组合

思路：
从矩阵左上角走到矩阵右下角，总共需要往下走m−1步，往右走n−1步，不同的走法路径在于往下和往右的组合情况；

即在一堆往下和往右的序列中，每种排列的情况，序列一共有m+n−2个位置，
选择其中n−1个位置作为往下，即不同的走法有

这里公式分母为啥多了另一半的阶乘呢？ 因为分子写成了阶乘，分母要除去多乘的部分。

具体做法：

step 1：分子分母从1开始；
step 2：按照公式累乘相除。

int uniquePaths(int m, int n) {
        long res = 1;
        for(int i=1;i<n;i++) //i从1到n-1
           res = res * (m-1 + i)/i; //res *= (m-1 + i)/i; //这样写为啥部分不通过呢？
        return res;   
    }
1
2
3
4
5
6

如果选择其中m−1个位置组合，公式如下；结果是一样的

 int uniquePaths(int m, int n) {
        long res = 1;
        //(m+n-2)!/[(m-1)!*(n-1)!]
        for(int i=n,j=1;j<m;i++,j++) 
           res = res * i/j; //这里(m+n-2)，设计十分巧妙
        //这里i从n开始累加m-1个数？其实第一次进入循环，并没有累加，而是从j=2开始累加到j=m-1;是积累加了m-2次，最后i=m+n-2，j=m-
        return res;    
    }
1
2
3
4
5
6
7
8

3.2 从起点走到终点，有多少种走法（有障碍物）

只能向右或向下走；
从起点走到终点，有多少种走法；

红色是障碍物，要绕行；

3.1 递归思路

和斐波拉切很像

这样也会有重复计算，需要记忆化，计算过的不再计算；

递推
从终点开始往起点推

状态转移方程

3.3 矩阵的最小路径和

描述
给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

数据范围: 1≤n,m≤500，矩阵中任意值都满足 0 <= ai,j <=1000;
​
要求：时间复杂度 O(nm)

例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，
所选择的最小累加和路径如下图所示：

 int minPathSum(vector<vector<int> >& matrix) {
        //write code here
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<int>> dp(n,vector<int>(m,0));
        dp[0][0] = matrix[0][0];
        //dp[i][j]表示以当前i，j位置为终点的最短路径长度
        //处理第一列
        for(int i=1;i<n;i++)
              dp[i][0] = matrix[i][0] + dp[i-1][0];
         //处理第一行   
        for(int j=1;j<m;j++)
              dp[0][j] = matrix[0][j] + dp[0][j-1];
         //其他行       
        for(int i=1;i<n;i++){
             for(int j=1;j<m;j++){      
                dp[i][j] = matrix[i][j] + min(dp[i - 1][j] , dp[i][j - 1]);
            }
        }   
        return dp[n-1][m-1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行时间30~35ms,
占用内存3800~3900多

不申请新的数组直接用原来的数组也行——对比测试证明，占用空间减少了很多

int minPathSum(vector<vector<int> >& matrix) {
        //write code here
        int n = matrix.size();
        int m = matrix[0].size();
    
        //dp[i][j]表示以当前i，j位置为终点的最短路径长度
        //处理第一列
        for(int i=1;i<n;i++)
              matrix[i][0] = matrix[i][0] + matrix[i-1][0];
         //处理第一行   
        for(int j=1;j<m;j++)
              matrix[0][j] = matrix[0][j] + matrix[0][j-1];
         //其他行       
        for(int i=1;i<n;i++){
             for(int j=1;j<m;j++){      
                matrix[i][j] = matrix[i][j] + min(matrix[i - 1][j] , matrix[i][j - 1]);
            }
        }   
        return matrix[n-1][m-1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

提交，运行占用内存对比，这种没有单独申请数组，占用内存少1000左右；运行时间差不多；
运行时间30~35ms,
占用内存2800~2900多

4 笔试题： 爬楼梯

描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：1≤n≤40
要求：时间复杂度：O(n)，空间复杂度： O(1)

4.1 斐波拉切递归

  int jumpFloor(int number) {
        return number <2 ?1 : jumpFloor(number-1) + jumpFloor(number - 2);
    }
1
2
3

要求：时间复杂度：O(n)，空间复杂度： O(n)

优化

int jumpFloor(int number) {
        int dp[50]{0};
        dp[0]=1,dp[1]=1;
        for(int i=2;i<=number;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp[number];
    }
1
2
3
4
5
6
7

只需要三个变量 ，dp[i]=dp[i-1]+dp[i-2];
是常数的内存消耗，O(1)

这里下标是从1开始的，所以包含n;如果下标从0开始

         //dp[0]=1,dp[1]=1;
         //for(int i=2;i<=number;i++) 
        //    dp[i]=dp[i-1]+dp[i-2];
        // return dp[number];
1
2
3
4

//如果for循环下标从0开始
//修改如下

dp[0]=1,dp[1]=2;
for(int i=2;i<number;i++) 
    dp[i]=dp[i-1]+dp[i-2];
return dp[number-1];
1
2
3
4

下面的程序中的 if 其实可以不用写

5 笔试题： 三角形最小路径和

5.1 实现1

最简单的实现代码（简洁，好记）

把三角形看成这种直角三角形，下标好分析

 int minimumTotal(vector<vector<int>>& triangle) {
        //自下而上，即从三角形底部开始向上转移，问题就简单多了

        for(int i=triangle.size()-2;i>=0;i--)
            for(int j=0;j<triangle[i].size();j++){
                triangle[i][j] +=  min(triangle[i+1][j] , triangle[i+1][j+1]);
            }
              
        //循环到达三角形定点结束，即第0层      
        return triangle[0][0]; //返回顶点的值（从底部到达顶部的路径和）
    }
1
2
3
4
5
6
7
8
9
10
11

5.2 实现2

巧妙用一维数组存储结果，空间复杂O(n)

（问题，实现1代码，没有申请数组，直接使用原数组，那是不是没有使用额外空间呢？）

 int minimumTotal(vector<vector<int>>& triangle) {
        //自下而上，即从三角形底部开始向上转移，问题就简单多了  
//巧妙用一维数组存储结果，空间复杂O(n)
        vector<int> dp = triangle[triangle.size() - 1];//并用三角形最后一层初始化数组
        for(int i=triangle.size()-2;i>=0;i--)
            for(int j=0;j<triangle[i].size();j++)
               dp[j] = min(dp[j],dp[j+1]) + triangle[i][j];
              
        //循环到达三角形定点结束，即第0层      
        return dp[0];
    }
1
2
3
4
5
6
7
8
9
10
11

5.3 实现3

巧妙用一维数组存储结果，空间复杂O(n)；
（问题，实现1代码，没有申请数组，直接使用原数组，那是不是没有使用额外空间呢？）

  int minimumTotal(vector<vector<int>>& triangle) {
        //自下而上，即从三角形底部开始向上转移，问题就简单多了  

         vector<int> dp(triangle.back());//巧妙用一维数组存储结果，空间复杂O(n)
        for(int i = triangle.size() - 2; 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