代码随想录二刷|动态规划3

dp动态规划

动态规划五步曲

动态规划数组的含义 dp[i]

递推公式

动态规划数组的初始化

确定遍历顺序

手动模拟验证

动态规划遇到问题要打印dp数组，看和模拟结果哪里不一样

一 基础问题

斐波那契数

题干

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

思路

（1）dp[i]表示i的斐波那契数

（2）转移公式：dp[i]=dp[i-1]+dp[i-2]

（3）初始条件 ：dp[0]=0 dp[1]=1

（4）从前向后遍历

要先排除不能使I-2有效的

class Solution {
public:
    int fib(int n) {
        vector<int>dp(n+1,0);
        dp[0]=0;
        if(n>=1)dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

爬楼梯

题干

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路

（1）dp[i]表示到第i阶的方法数

（2）转移公式：dp[i]=dp[i-1]+dp[i-2]

（3）初始条件 ：dp[0]=1 dp[1]=1 （dp[0]表示到达地面的方法数)

（4）从前向后遍历

class Solution {
public:
    int climbStairs(int n) {
        if(n<2)return 1;
        vector<int>dp(n+1,0);
        dp[1]=1;
        dp[0]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

使用最小花费爬楼梯

题干

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

思路

（1）dp[i]表示走到第i个台阶（下标为i的台阶）最小花费

（2）转移公式

dp[i]=min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2])

如果一次走一个，那么从i-1出发需要支付cost[i-1]和到i-1的最小花费dp[i-1]；一次走2个，那么从i-2出发需要支付cost[i-2]和到i-2的最小花费dp[i-2]

（3）初始化：可以从下标为0或1出发，所以，dp[0]=0 dp[1]=0

（4）从前向后遍历

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int>dp(cost.size()+1,0);
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<=cost.size();i++)
        {
            dp[i]=min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2]);
        }
        return dp[cost.size()];
    }
};

不同路径

题干

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

思路

（1）dp[i][j] 是到达（i，j）的路径数

（2）递推：dp[i][j]=dp[i-1][j]+dp[i][j-1];

（3）初始化：如果是第一行或第一列，就必须沿着一条直线走，所以初始化为1

（4）从左上到右下

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(n<=1 || m<=1)return 1;
        int dp[m][n];
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++ ){
            dp[0][i]=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];
    }
};

不同路径II

题干

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

思路

（1）dp[i][j] 是到达（i，j）的路径数

（2）递推：

如果（i，j）不是障碍，那么就可以递推dp[i][j]=dp[i-1][j]+dp[i][j-1];

如果（i，j）是障碍，那么就赋值为0，因为不可到达

（3）初始化：如果是第一行或第一列，就必须沿着一条直线走，如果遇到障碍那么障碍自己和后面的点都赋值为0，没遇到过障碍就赋值为1

（4）从左上到右下

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

整数拆分

题干

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

思路

（1）dp[i] i拆分后最大的乘积

（2）递推：dp[i]=max(max(dp[i-j]*j,(i-j)*j),dp[i])

从1到i-1遍历j，表示从i中拆分出来的数

1）如果只拆成两个，那么就是j*(i-j)

2）如果拆的更多，就要考虑怎么拆i-j，i-j拆分后最大的乘积dp[i-j]，所以在拆的个数大于2的时候最大的乘积是j*dp[i-j]

3）和之前的dp[i]相比较

（3）初始化：0和1在拆分中没有意义，所以从i=2开始初始化

（4）从3开始遍历i

class Solution {
public:
    int integerBreak(int n) {
        vector<int>dp(n+1,0);  
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i]=max(max(dp[i-j]*j,(i-j)*j),dp[i]);
            }
        }
        return dp[n];
    }
};

不同的二叉搜索树

题干

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

思路

（1）dp[i] 从1到i元素构成的二叉搜索树的个数

（2）递归

对于每一个i，讨论作为根节点的元素j

1）左子树有j-1个节点，是[1,j-1]构成的，最多dp[j-1]种

2）右子树有i-j个节点，是[j+1,i]构成的。[j+1,i]构成的二叉搜索树个数等于[1,i-j]构成的二叉搜索树个数，最多dp[i-j]种

根节点为j时，有dp[j-1]*dp[i-j]种

（3）初始化：dp[0]=1（空相当于1种），dp[1]=1

（4）遍历：i从2开始遍历到n

class Solution {
public:
    int numTrees(int n) {
        vector<int>dp(n+1,0);
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
};

二 背包问题

理论基础

01背包

01背包题目模板

你有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大

二维dp数组

（1）dp[i][j]表示在物品[0,i]中任意取，装进容量为j的背包，最大的价值之和

（2）递推公式

dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

讨论是否放物品i

1）不放物品i，就是在物品[0,i-1]中任意取，装进容量为j的背包，能有的最大价值

2）放物品i，先从容量j里面留出来物品i的重量，再在物品[0,i-1]中任意取，装进容量为j-weight[i]的背包，再加上i的价值

（3）初始化

1）背包容量为0（j=0），dp为0

2）只考虑第一个物品，也就是i=0

j<weight[0] 的，dp[0][j]=0

j>=weight[0] 的，dp[0][j]=value[0]

（4）遍历次序

i从1到n，j从0到背包最大容量

先i后j，先j 后i都可

一维dp数组

相当于dp数组去掉i这个维度，并且限定必须先遍历物品i，后遍历容量j，并且容量从大到小遍历，物品从小到大遍历

为什么dp数组可以改成一维

因为二维数组dp[i][j]要么等于dp[i-1][j]，要么等于dp[i-1][j-weight[i]]+value[i]

所以dp[i][j]只和dp[i-1]有关

在考虑dp[i][j]的时候，dp[i][j]就是dp[i-1][j]（因为还没改过），只要他的左边（j更小）的数据还保持i-1的状态，那么就可以去掉i这一表示物品的维度，只留下j也可以实现

（1）dp[j]

装进容量为j的背包，最大的价值之和

（i这个维度还会遍历，表示在物品[0,i]中任意取）

（2）递推公式

dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

（3）初始化

dp全初始化为0

**原因：**求dp[j]的时候，需要在dp[j]和dp[j-weight[i]]+value[i]里面取大的，所以希望dp[j]小于所有的重量，所以取0

让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了

（4）遍历顺序

必须先遍历物品i，后遍历容量j，并且容量从大到小遍历（最大容量到weight[i]），物品从小到大遍历（从0到n）

原因：

1）为什么背包容量倒序遍历

倒序遍历是为了保证物品i只被放入一次，也就是i时的dp[j]的产生是由i-1的结果而来，而不受到i的干扰

i对应的dp[j]是由i-1的dp[j]和i-1的dp[j-weight[i]]决定的，所以更新dp[j]的时候，需要确保dp[j-weight[i]]还是i-1所对应的，因此从后向前遍历j

• 如果正序遍历，如果dp[j]小于dp[j-weight[i]]+value[i]，那么dp[j]最终取dp[j-weight[i]]+value[i]，而dp[j-weight[i]]可能也是在max的2个选项中选了后者,加过value[i]，也就不是i-1对应的dp[j-weight[i]]，对于dp[j]来说value[i]就被加了两次
• 如果倒序遍历，先处理较大的j，即使较大的j的dp[j]更新为dp[j-weight[i]]+value[i]，那么也不会对更小的j对应的dp[j]造成影响，因为影响dp[j]只有前面更小的j的dp[j]在i-1的遍历产生的结果

e.g.

物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

i=0

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历

倒序遍历

i=0

dp[2]=max(dp[2],dp[2 - weight[0]] + value[0])=dp[2 - weight[0]] + value[0]=15

dp[1]=max(dp[1],dp[1 - weight[0]] + value[0])=dp[1- weight[0]] + value[0]=15

2）为什么不可以先遍历背包容量

一维dp数组是滚动更新的数组，如果先遍历背包容量，那么dp保存的就是单个物品的价值

先遍历背包相当于二维dp数组得到一列的值，我们无法根据j-1的值计算j的值，

分割等和子集

题干

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

思路

（1）背包模型：

物品：第i个数

价值：nums[i]

重量：nums[i]

背包最大容量 sum/2 （提前排除掉sum为奇数的情况）

（2）有等和子集===最大容量 sum/2的背包被装满

dp[sum/2 ]是背包容量为sum/2 的最大价值。如果背包容量为sum/2 的最大价值是sum/2 ，那么就是被装满了，也就是存在和为sum/2 是子集

因为重量和价值一比一，所以背包容量为sum/2 的最大价值是多少，这些数字的和就是多少（也就是总重是多少），如果和是sum/2，就是等和子集

class Solution {
public:

    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
        }
        if(sum%2)return false;
        vector<int>dp(sum/2+1,0);
        for(int i=0;i<nums.size();i++){
            for(int j=sum/2;j>=nums[i];j--){
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[sum/2]==sum/2;
    }
};