文章目录

动态规划
- 基础题

动态规划

动规五部曲：

确定dp数组以及下标含义；
确定递推公式；
dp初始化；
确定遍历的顺序；
举例推导dp数组；

基础题

509 fibonacci

确定dp数组以及下标含义； dp[i]表示第i个fibonacci数
确定递推公式；dp[i]=dp[i-1]+dp[i-2]
dp初始化；dp[1]=0,dp[2]=1
确定遍历的顺序；从1到n
举例推导dp数组；dp[3]=dp[2]+dp[1]=2

70 爬楼梯

需要计算爬n阶楼梯的方法：

确定dp数组以及下标含义； dp[i]表示爬i阶楼梯的方法
确定递推公式；dp[i]=dp[i-1]+dp[i-2] 可以从dp[i-1]爬一阶，也可以从dp[i-2]爬两阶
dp初始化；dp[1]=1,dp[2]=2
确定遍历的顺序；从1到n
举例推导dp数组；dp[3]=dp[2]+dp[1]=3

一点疑惑

为什么不是：dp[i]=dp[i-1]+dp[i-2]*2 从dp[i-2]到达dp[i]有两种方法啊，走一次2阶，或者走两次1阶？
dp[0]=1?

答

dp[i-2]走2次1阶的过程：首先走1次1阶到达了dp[i-1],然后从dp[i-1]走1次1阶到达了dp[i] ;因此这一次已经算入了上面从从dp[i-1]爬一阶到达dp[i]的过程中；仔细想想再相加就是冗余了；
之前看力扣上面的解答，说dp[0]=1是为了后续从i=2就可以开始递推，然而，今天看了作者Carl的讲解，dp[0]就是没有意义的，我们直接从dp[1]开始定义dp；觉得这样一解释，真的通俗易懂，只是多浪费一个int而已；并且在最后，用两个常数来优化空间，也不存在浪费的情况；

746 使用最小花费爬楼梯

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

还是一样，五部曲

确定dp数组以及下标含义； dp[i]表示爬上i阶楼梯消耗的体力
确定递推公式；dp[i]=min(dp[i-1],dp[i-2])+cost[i]
dp初始化；dp[0]=cost[0],dp[1]=cost[1]
确定遍历的顺序；从0到n-1
举例推导dp数组；

疑惑

为什么递推公式是+cost[i],而不是min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]) ?

因为，题目说，每爬上一个阶梯都要花费对应的体力值，爬上了才花费，爬上后可以选择往上走一阶还是走两阶；看力扣评论区有一个不错的解释：每个台阶上有不同数量的金坷垃，你到指定的台阶上后，想要继续往上走，就必须eat掉这些金坷垃，那dp[i]就表示，到达台阶i并且想要继续往上爬，吃的最少的金坷垃；所以，到达最终的楼层，不需要你吃屎，那么，最终吃的最少的屎就是min(dp[cost.size()-1],dp[cost.size()-2])

class Solution {
   
public:
    int minCostClimbingStairs(vector<int>& cost) {
   
        //dp[i]=min(dp[i-1],dp[i-2])+cost[i];
        //dp[i]表示爬上阶梯i需要花费的体力
        vector<int> dp(cost.size(),0);
        dp[0]=cost[0];
        dp[1]=cost[1];
        for(int i=2;i<cost.size();++i)
        {
   
            dp[i]=min(dp[i-1],dp[i-2])+cost[i];
        }
        return min(dp[cost.size()-1],dp[cost.size()-2]);//上最后一个阶梯，不需要耗费体力
    }
};

62 不同路径

⼀个机器⼈位于⼀个 m x n ⽹格的左上⻆（起始点在下图中标记为 “Start” ）。机器⼈每次只能向下或者向右移动⼀步。机器⼈试图达到⽹格的右下⻆（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

dp[i][j] ：到达位置(i,j) 的不同路径数

dp[i][j]=dp[i-1][j]+dp[i][j-1] ：到达位置(i,j) 可以从(i-1,j) 向下走一步，或者从(i,j-1) 向右走一步；

class Solution {
   
public:
    int uniquePaths(int m, int n) {
   
        //dp[i][j]表示到达位置(i,j)的不同路径和
        //dp[i][j]=dp[i-1][j]+dp[i][j-1]
        vector<vector<int>> dp(m,vector<int>(n,1));
        for(int 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];

    }
};

时间复杂度是O(mn)，空间复杂度也是O(mn)

可以采用滚动数组的方法，将空间复杂度变为O(n);

class Solution {
   
public:
    int uniquePaths(int m, int n) {
   
        //dp[i][j]表示到达位置(i,j)的不同路径和
        //dp[i][j]=dp[i-1][j]+dp[i][j-1]
        vector<int> dp(n,1);
        for(int i=1;i<m;++i)
        {
   
            for(int j=1;j<n;++j)
            {
   
                dp[j]+=dp[j-1];
            }
        }
        return dp[n-1];
    }
};

63 不同路径II

⼀个机器⼈位于⼀个 m x n ⽹格的左上⻆（起始点在下图中标记为“Start” ）。机器⼈每次只能向下或者向右移动⼀步。机器⼈试图达到⽹格的右下⻆（在下图中标记为“Finish”）。现在考虑⽹格中有障碍物。那么从左上⻆到右下⻆将会有多少条不同的路径？

class Solution {
   
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
   
        //dp[i][j]=dp[i-1][j]+dp[i][j-1]
        vector<vector<int>> dp(obstacleGrid.size(),vector<int>(obstacleGrid[0].size(),0));
        if(!obstacleGrid[0][0]) 
            dp[0][0]=1;
        else 
            return 0;
        for(int i=1;i<obstacleGrid.size();++i)
        {
   
            if(obstacleGrid[i][0]) break;
            dp[i][0]=1;
        }
        for(int j=1;j<obstacleGrid[0].size();++j)
        {
   
            if(obstacleGrid[0][j]) break;
            dp[0][j]=1;
        }
        
        for(int i=1;i<obstacleGrid.size();++i)
        {
   
            for(int j=1;j<obstacleGrid[0].size();++j)
            {
   
                if( obstacleGrid[i][j] || (obstacleGrid[i-1][j]&&obstacleGrid[i][j-1]) )
                {
   //本身是障碍物，或者左边和上面都是障碍物
                    continue;
                }
                else
                {
   
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[obstacleGrid.size()-1][obstacleGrid[0].size()-1];

    }
};

递推公式还是和上题一样，只是当遇到上面和左边都是障碍物的时候，保持默认值0；
当入口是障碍物的时候，直接返回0；

注意：判断满足某一个条件就退出，不用用while来判断，break只能向外跳出一层；

343 整数拆分

给定⼀个正整数 n，将其拆分为⾄少两个正整数的和，并使这些整数的乘积最⼤化。返回你可以获得的最⼤乘积。示例 1: 输⼊: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。示例 2: 输⼊: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。说明: 你可以假设 n 不⼩于 2 且不⼤于 58。

这一道题目其实有点难想，尤其是，当我用dp[i]表示数字i拆分得到的最大乘积后，不知道递推关系式应该如何写。

看了答案后也有点疑惑，dp[i]=max(dp[i],dp[i-j]*j,(i-j)*j)

然后，我思考可以从暴力枚举的角度解释：

我们可以把数字n拆成n=i+j,对于 i 我们可以从3开始遍历，然后对应的j也就确定了；相应的对于每一个j，也可以进行拆分，拆分的结果已经存储在dp中

class Solution {
   
public:
    int integerBreak(int n) {
   
        //dp[i]表示拆分i可以得到的最大乘积
        vector<int> dp(n+1);
        dp[2]=1;
        for(int i=3;i<=n;++i)
        {
   
            for(int j=1;j<i-1;++j)
            {
   
                dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j));
            }
        }
        return dp[n];
    }
};

疑问：这个地方为什么是<i-1 而不是<i?

答：因为初始值只有dp[2] ,所以，能够被拆的(i-j) 最小也只能到2 ，那么 j最大也就只能等于i-2了；

96 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

第一眼看上去，竟然想用回溯法，emm开始没有注意到二叉搜索树：左子树元素值小于根节点，右子树元素值大于根节点；读懂题目意思后，就要开始思考，如何解决；按照作者的思考路径，首先分析了1个节点，2个节点排列，然后发现3个节点的排列是前面的组合，考虑可以使用子问题覆盖新问题，于是推出可以使用动态规划。

确定dp数组以及下标含义； dp[i]表示 n个节点组成的满足题目条件的二叉搜索树有多少种
确定递推公式；dp[i]+=dp[j-1]*dp[i-j]
dp初始化；dp[0]=1 这个是从dp[1]得出来的，dp[1]=dp[0]*dp[0]
确定遍历的顺序；i从1到n，j从1到i
举例推导dp数组；

class Solution {
   
public:
    int numTrees(int n) 
    {
   
        //二叉搜索树 左子树所有元素小于根节点，右子树所有元素大于根节点
        //dp[i] 表示n个节点组成的满足题目条件的二叉搜索树有多少种
        // 递推公式： dp[i]+=dp[j-1]*dp[i-j]
        // 初始化 dp[0]=1;
        vector<int> dp(n+1);
        dp[0]=1;
        for(int i=1;i<n+1;++i)
            for(int j=1;j<=i;++j)
                dp[i]+=dp[j-1]*dp[i-j];
        return dp[n];
    }
};

冲就完事了.

总结：动态规划（1） 基础题型，动规五部曲