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

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都可

模板

  vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    for(int i = 1; i < weight.size(); i++) { 
        for(int j = 0; j <= bagweight; j++) { 
            if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }

为什么j的遍历不从nums[i]开始，因为在j<nums[i]的情况下，dp[i][j] = dp[i - 1][j]

一维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）

模板

 vector<int>dp(bag+1,0);
 for(int i=0;i<weight.size();i++){
            for(int j=bag;j>=nums[i];j--){
                dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }

j最小遍历值为nums[i]，是因为如果j小于nums[i]，那么dp[j]还是dp[j]

原因理解：

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

倒序遍历是为了保证物品i只被放入一次，也就是i时的dp[j]的产生是由i-1的结果而来，而不受到i的干扰。用来求dp[j]的dp[j-weight[i]]，实际上是dp[i-1][j-weight[i]]，不可以在计算dp[j]之前更新

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的值，

完全背包

完全背包题目模板

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是每种物品有无限件。

二维解法

（1）dp数组

dp[i][j]表示在[0,i]的物品范围内选取，背包容量为j的最大总价值

（2）递推

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

两种情况

1）不取i：从前[0,i-1]个物品中选取，背包容量为j的最大总价值

2）取i：等于i的价值+取i之前的最大总价值，取i之前可以取[0,i-1]也可以取i（因为i有多个）所以第一个下标是i，留出i的重量所以第二个下标是j-weight[i]

（如果j<weight[i]，那么dp[i][j]=dp[i-1][j]）

（3）初始化

dp[0][j]：只考虑第一个物品，那么只要背包年呢个装下，就不停的装第一个物品

for (int j = weight[0]; j <= bagWeight; j++)
    dp[0][j] = dp[0][j - weight[0]] + value[0];

dp[i][0]：初始化为0，因为什么都装不了

（4）遍历

先i后j，先j 后i均可

代码模板

vector<vector<int>>dp(weight.size(),vector<int>(bagsize+1,0));
for (int j = weight[0]; j <= bagWeight; j++)
    dp[0][j] = dp[0][j - weight[0]] + value[0];
for(int i=1;i<weight.size();i++){
	for(int j=0;j<=bagsize;j++){
		if(j>=weight[i])dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);
		else dp[i][j]=dp[i-1][j];
	}
}
return dp[weight.size()-1][bagsize];

一维解法

（1）dp数组

dp[j]表示在[0,i]的物品范围内选取，背包容量为j的最大总价值

（2）递推

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

两种情况

1）不取i：从前[0,i-1]个物品中选取，背包容量为j的最大总价值

2）取i：等于i的价值+取i之前的最大总价值，取i之前可以取[0,i-1]也可以取i（因为i有多个）所以第一个下标是i，留出i的重量所以第二个下标是j-weight[i]

（如果j<weight[i]，那么dp[j]=dp[j]）

简化版本：

for(int i=1;i<weight.size();i++){
	for(int j=weight[i];j<=bagsize;j++){
		dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
	}
}

（3）初始化

dp[0]=0 容量为0,就什么都放不了

（4）遍历

容量从小到大遍历

1）为什么容量从小到大遍历

因为用来计算dp[j]的dp[j-weight[i]]实际是dp[i][j-weight[i]]，本来就要先更新dp[j-weight[i]]为i对应的情况（考虑[0,i]）

2）纯完全背包问题，i和j哪个在外层都可以

是因为都不影响计算dp[j]所需要的值dp[j-weight[i]]，在计算dp[j]之前dp[j-weight[i]]就被计算好了

（图来自代码随想录）

3）特定题目，对i和j遍历先后顺序有要求

如果求组合数：就是外层for循环遍历物品，内层for遍历背包
如果求排列数：就是外层for遍历背包，内层for循环遍历物品

假设：wieght[0] = 1，wieght[1] = 5。

先遍历物品：那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。所以先遍历物品中dp[j]里计算的是组合数

先遍历背包：那么在同一个背包容量下，可以选择0号或1号，前一个选的也可以是0号或1号，所以会考虑到{1,5}和{5,1}。所以这先遍历背包中dp[j]里计算的是排列数

求最小数：外层for循环遍历物品和外层for循环遍历背包都可以

因为排列数和组合数都是全部情况的个数，必须不重复；而最小数不需要担心重复，只需要不缺漏就可以

代码模板

vector<int>dp(bagsize+1,0);
for(int i=1;i<weight.size();i++){
	for(int j=weight[i];j<=bagsize;j++){
		dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
	}
}
return dp[weight.size()-1][bagsize];

多重背包

多重背包题目模板

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

解法

把多重背包看成01背包的变体，物品数量不是一的，都展开，看成不同物品

代码

int bagWeight,n;
    cin >> bagWeight >> n;
    vector<int> weight(n, 0); 
    vector<int> value(n, 0);
    vector<int> nums(n, 0);
    for (int i = 0; i < n; i++) cin >> weight[i];
    for (int i = 0; i < n; i++) cin >> value[i];
    for (int i = 0; i < n; i++) cin >> nums[i];    
    
    for (int i = 0; i < n; i++) {
        while (nums[i] > 1) { // 物品数量不是一的，都展开
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }
 
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品，注意此时的物品数量不是n
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

频繁的push_back费时间，更节约时间的做法：加一层遍历个数

int bagWeight,n;
    cin >> bagWeight >> n;
    vector<int> weight(n, 0);
    vector<int> value(n, 0);
    vector<int> nums(n, 0);
    for (int i = 0; i < n; i++) cin >> weight[i];
    for (int i = 0; i < n; i++) cin >> value[i];
    for (int i = 0; i < n; i++) cin >> nums[i];

    vector<int> dp(bagWeight + 1, 0);

    for(int i = 0; i < n; i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            // 以上为01背包，然后加一个遍历个数
            for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
    }

1、01背包

分割等和子集

题干

给你一个 只包含正整数 的非空数组 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 是子集

因为重量和价值一比一，所以背包容量为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;
    }
};

最后一块石头的重量II

题干

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1]
输出：1

解释：

组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

思路

（1）尽量让石头分成重量相同的两堆（尽可能相同），相撞之后剩下的石头就是最小的

（2）尽可能拼成重量为 sum / 2 的石头堆,这样剩下的石头堆也是尽可能接近 sum/2 的重量

（3）也就是将重量小于sum/2的石头，放进容量sum/2的背包，尽可能让包里的石头重量和大（接近sum/2）)

public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(int i=0;i<stones.size();i++){
            sum+=stones[i];
        }
        vector<int>dp(sum/2+1,0);
        for(int i=0;i<stones.size();i++){
            for(int j=sum/2;j>=stones[i];j--){
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-dp[sum/2]-dp[sum/2];
    }
};

目标和

题干

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

思路

因为感觉到有递推，也就是后面选择符号受到前面的影响，所以用动态规划

（1）方法1

在这个方法中，为每个元素选择+或-，不能不选

1）dp[i][j]

i nums下标

j j-1000表示数字和（因为target最小值-1000,所以整体加1000）

dp[i][j]表示考虑下标[0,i]的nums数字，和为j-1000的最大方法数

2）递推

dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]

（nums[i]前面要么加+，要么加-）

具体需要约束下标范围，避免越界：

bag=max(sum+1000,target+1000)

if (j + nums[i] <= bag && j - nums[i] >= 0)    dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]];

else if (j + nums[i] > bag && j - nums[i] >= 0)   dp[i][j] = dp[i - 1][j - nums[i]];

else if (j + nums[i] <= bag && j - nums[i] < 0)    dp[i][j] = dp[i - 1][j + nums[i]];

3）初始化

如果只考虑第一个元素，那么只有和为nums[0]或-nums[0]的情况有一个方法，其他的都没有方法

dp[0][nums[0] + 1000] += 1; dp[0][-1 * nums[0] + 1000] += 1;

选择加1而不是赋值，是为了处理第一个元素是0的情况

4）遍历

i：从小到大

j：从小到大，上限bag=max(sum+1000,target+1000)，是为了包含所有可能的情况

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
        }
        int bag = max(target + 1000, sum + 1000);
        vector<vector<int>> dp(nums.size(), vector<int>(bag + 1, 0));
        dp[0][nums[0] + 1000] += 1;
        dp[0][-1 * nums[0] + 1000] += 1;//对于第一个元素是0的情况，如果单纯赋值，就会少算一个
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j <= bag; j++) {
                if (j + nums[i] <= bag && j - nums[i] >= 0)
                    dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]];

                else if (j + nums[i] > bag && j - nums[i] >= 0)
                    dp[i][j] = dp[i - 1][j - nums[i]];
                else if (j + nums[i] <= bag && j - nums[i] < 0)
                    dp[i][j] = dp[i - 1][j + nums[i]];
                // else dp[i][j]=dp[i-1][j];
            }
        }
        return dp[nums.size() - 1][target + 1000];
    }
};

（2）方法2：

假设加法的总和为x，那么减法对应的总和就是sum - x，要求的是 x - (sum - x) = target，所以2x=(target + sum) ，x = (target + sum) / 2

所以求怎样分配+号

在这个方法中，选择加+号的元素，可以不选

0）排除没有答案的情况

<1> 2x=(target + sum)，如果target + sum是奇数，就没有答案

<2>如果target 的绝对值已经大于sum，就是没有答案

1）dp[i][j]

i nums下标

j 表示加法的总和

dp[i][j]表示考虑下标[0,i]的nums数字，加法的总和为j的最大方法数

2）递推公式

dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]

如果nums[i]前面加+号，那么之前考虑[0,i-1]的时候需要和为j-nums[i]，才可以使得考虑[0,i]的时候和为j

3）初始化

<1>dp[i][0]

在这个方法中，选择加+号的元素，可以不选，所以对于j=0的情况，不选也算是一种方法，因此初始化为1

注意，如果元素有0

比如前两个数字都是0，nums[0]=0， nums[1]=0，和为0的方法有几种。

nums[0]和 nums[1]都不加+号
nums[0]加+号，nums[1]不加
nums[0]不加， nums[1]都加+号
nums[0]和 nums[1]都加+号

此时是有4种方法。dp[1][0]=4

其实就是算数组里有t个0，然后按照组合数量求，即 2^t 。

<2> dp[0][j]

dp[0][Nums[0]]=1(前提是nums[0]小于等于x)，其他为0

4）遍历

都从小到大遍历

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
        }
        if(sum<abs(target))return 0;
        if((sum + target)%2)return 0;
        int x = (sum + target) / 2;
        vector<vector<int>> dp(nums.size(), vector<int>(x + 1, 0));
        if (nums[0] <=x)dp[0][nums[0]] = 1;
        
        int zero = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0)
                zero++;
            dp[i][0] = pow(2, zero);
        }

        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j <= x; j++) {
                if (j >=nums[i])
                    dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[nums.size() - 1][x];
    }
};

（3）方法2 一维数组

1）d[j]

j 表示加法的总和

dp[j]表示考虑下标[0,i]的nums数字，加法的总和为j的最大方法数

2）递推

dp[j] = dp[j - nums[i]] + dp[j]

3）初始化

dp[0] = 1 因为在最开始的时候，取+号的和为0只有一种肯可能性（不选则元素加+号）

4）遍历

i从0到size

j从x到nums[i]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
        }
        if(sum<abs(target))return 0;
        if((sum + target)%2)return 0;
        int x = (sum + target) / 2;
        vector<int> dp(x + 1, 0);
        dp[0]=1；
        for (int i = 0; i < nums.size(); i++) {
            for (int j=x; j >=nums[i]; j--) {
                    dp[j] = dp[j - nums[i]] + dp[j];
            }
        }
        return dp[x];
    }
};

一和零

题干

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

思路

（1）首先，记录每个字符串当中多少个1,多少个0

（2）是否选择某一个字符串，和已经选了那些字符串有关，所以是动态规划

（3）背包

1）dp[j][k]

在考虑[0,i]的元素的时候，1最多j个，0最多k个的最大的子集长度

2）递推

dp[j][k] = max(dp[j][k], dp[j - zeros[i]][k - ones[i]] + 1)

选择是否将第i个字符串加到子集里面，

不加，就是[0,i-1]区间上1最多j个，0最多k个的最大的子集长度；加，就是就是[0,i-1]区间上1最多j-zeros[i]个，0最多k-ones[i]个的最大的子集长度再加上1。两者取大的。

3）初始化：全是0

4）遍历

i从小到大

j从m开始，到zeros[i]，k从n开始，到ones[i]

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<int> zeros(strs.size(), 0);
        vector<int> ones(strs.size(), 0);
        for (int i = 0; i < strs.size(); i++) {
            for (int j = 0; j < strs[i].size(); j++) {
                if (strs[i][j] == '1')
                    ones[i]++;
                else
                    zeros[i]++;
            }
        }
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < strs.size(); i++) {
            for (int j = m; j >= zeros[i]; j--) {
                for (int k = n; k >= ones[i]; k--) {
                    dp[j][k] = max(dp[j][k], dp[j - zeros[i]][k - ones[i]] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

2、完全背包

零钱兑换II

题干

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

思路

二维

（1）dp[i][j]只考虑[0,i]的硬币，总金额为j的方法数

uint64_t：有的测试用例超出long long

（2）递推

两种情况求和

1）不放i：dp[i-1][j]种

2）放i：dp[i][j-coins[i]]种

（j<coins[i]的时候，dp[i][j]=dp[i-1][j]）

（3）初始化

1）dp[0][j]：只考虑第一个面额，那么只要总金额能被第一个面额整除，就不停的加第一个面额，算一种方法

for (int j = weight[0]; j <= bagWeight; j++)
    if(i%coins[0]==0)dp[0][i]=1;

2）dp[i][0]：初始化为1，不取硬币也是一种方法，使得总金额为0

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<vector<uint64_t>>dp(coins.size(),vector<uint64_t>(amount+1,0));
        for(int i=coins[0];i<=amount;i++){
            if(i%coins[0]==0)dp[0][i]=1;
        }
        for(int i=0;i<coins.size();i++){
            dp[i][0]=1;
        }
        for(int i=1;i<coins.size();i++){
            for(int j=0;j<=amount;j++){
                if(j>=coins[i])dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]];
                else dp[i][j]=dp[i-1][j];
            }
        }
        return dp[coins.size()-1][amount];
    }
};

一维

（1）dp[j]：金额和为j的情况数

uint64_t：有的测试用例超出long long

（2）递推：

如果不取i ，那么有dp[j]种；如果取i，那么有dp[j - coins[i]]种，求和

对于j < coins[i]的情况，用for循环的条件排除

（3）初始化

dp[0]=1 只有一种可能使得总金额为0,那就是什么也不装

（4）遍历

组合问题，先遍历i

假设：coins[0] = 1，coins[1] = 5。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<uint64_t> dp(amount + 1, 0); // 防止相加数据超int
        dp[0] = 1; // 只有一种方式达到0
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount]; // 返回组合数
    }
};

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<uint64_t> dp(target + 1, 0);
        dp[0] = 1;
        for (int j = 0; j <= target; j++) {
            for (int i = 0; i < nums.size(); i++) {
                if (j >= nums[i])
                    dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

组合总和IV

题干

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

请注意，顺序不同的序列被视作不同的组合。因此输出为 7。

思路

（1）dp[j]：和为j的情况数

uint64_t：有的测试用例超出long long

（2）递推：

如果不取i ，那么有dp[j]种；如果取i，那么有dp[j - nums[i]]种，求和

对于j < nums[i]的情况，只有dp[j]

（3）初始化

dp[0]=1 没有实际意义

（4）遍历

先遍历背包容量，后遍历物品

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<uint64_t> dp(target + 1, 0);
        dp[0] = 1;
        for (int j = 0; j <= target; j++) {
            for (int i = 0; i < nums.size(); i++) {
                if (j >= nums[i])
                    dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

爬楼梯（进阶）

题干

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

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入描述：输入共一行，包含两个正整数，分别表示n, m

输出描述：输出一个整数，表示爬到楼顶的方法数。

输入示例：3 2

输出示例：3

提示：

当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶段
1 阶 + 2 阶
2 阶 + 1 阶

思路

（1）dp[i]：到达第i阶的方法数

（2）迭代

dp[i]+=dp[i-j]

j表示这次走了j阶到达第i阶

（3）初始化

dp[0]=1 站在地上只有一种方法

（4）遍历顺序

先遍历i后遍历j

因为是到了某一级台阶才会开会i始讨论是一次走了几级台阶到这里的

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m;
    int n;
    cin>>n>>m;
    vector<int>dp(n+1,0);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m && j<=i;j++){
            dp[i]+=dp[i-j];
        }
    }
    cout<<dp[n];
    return 0;
}

零钱兑换

题干

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

思路

（1）dp[j]：钱总和是j的时候，最少的硬币数

（2）迭代

dp[j]=min(dp[j],dp[j-coins[i]]+1);

条件：dp[j-coins[i]]!=INT_MAX，如果dp[j-coins[i]]是INT_MAX，就说明j-coins[i]这个金额无法实现，也就不能在这个基础上加

（3）初始化

从j=1开始初始化成INT_MAX，dp[0]=0因为总金额为0的话不需要硬币

（4）遍历

求最小数：外层for循环遍历物品和外层for循环遍历背包都可以

遍历物品和背包的顺序是正序

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX);
        dp[0]=0;
        for(int i=0;i<coins.size();i++){
            for(int j=coins[i];j<=amount;j++){
                if(dp[j-coins[i]]!=INT_MAX)dp[j]=min(dp[j],dp[j-coins[i]]+1);
            }
        }
        if(dp[amount]==INT_MAX)return -1;
        else return dp[amount];
    }
};

完全平方数

题干

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

思路

（1）dp[j] j拆分成完全平方数的和之后，至少多少项

（2）递推

dp[j]=min(dp[j],dp[j-i*i]+1)

1）选择 i^2 : 在j-i*i的最小项数上加1

2）不选择：保持dp[j]

二者取大的

（3）初始化

dp[0]=0：单纯根据dp[1]=1推出来的

其他初始化为INT_MAX

（4）循环遍历

求最小数：外层for循环遍历物品和外层for循环遍历背包都可以

遍历物品和背包的顺序是正序（因为是完全背包，个数不限制）

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

    }
};

单词拆分

题干

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。

示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

思路

（1）dp[j]：s的从下标为0点开始的长为j的子串能否被构成

为什么不表示s[0,j]能否被构成：如果这样的话，dp[0]就是有实际意义的，需要另外找到一个值赋值为true（初始化没有dp[j]赋值为true的化，答案一定是false）

（2）递推

讨论是否选择第i个词wordDict[i]

1）如果前面长为 j - wordDict[i].size()的部分不可以构成，那么还是false

2）如果前面长为 j- wordDict[i].size()的部分可以构成，并且[j-wordDict[i].size(),j]的子串就是wordDict[i]，那么就可以构成，是true

string temp(s.begin() + j - wordDict[i].size(),
                                s.begin() + j);
if (dp[j - wordDict[i].size()] && temp == wordDict[i])
                        dp[j] = true;

（3）初始化

初始化成false，只有dp[0]是true

（4）遍历

1）先遍历物品再遍历背包不行

使用用例：s = “applepenapple”, wordDict = [“apple”, “pen”]

dp效果

因为用apple去遍历的时候，dp[8]不能被赋值成1,是因为pen还没遍历，所以dp[13]也就不能是1

代码：

class Solution {
public:
    
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool>dp(s.size()+1,false);
        dp[0]=true;
        for(int i=0;i<wordDict.size();i++){
            for(int j=wordDict[i].size();j<=s.size();j++){
                string temp(s.begin()+j-wordDict[i].size(),s.begin()+j);
                if(dp[j-wordDict[i].size()]&& temp==wordDict[i])dp[j]=true;
            }
        }
        return dp[s.size()];
    }
};

2）先遍历背包再遍历物品

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int j = 1; j <= s.size(); j++) {
            for (int i = 0; i < wordDict.size(); i++) {
                if(j>=wordDict[i].size()){
                    string temp(s.begin() + j - wordDict[i].size(),
                                s.begin() + j);
                    if (dp[j - wordDict[i].size()] && temp == wordDict[i])
                        dp[j] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

回溯法：超时

class Solution {
public:
    vector<string>ans;
    bool f(string s,int start,unordered_set<string>& wordSet,vector<bool> memory){
        if(start>=s.size()){
            return true;
        }
        if(memory[start]==false)return false; #如果从start开始的字符串都不可拆分，就跳过
        for(int i=start;i<s.size();i++){
            string sub(s.begin()+start,s.begin()+i+1);
            if(wordSet.find(sub)!=wordSet.end() && f(s,i+1,wordSet,memory))return true;
        }
        memory[start]=false;
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(),wordDict.end());
        vector<bool> memory(s.size(), 1);
        return f(s,0,wordSet,memory);
    }
};

三打家劫舍

1 基本思路

dp[i]=max(dp[i-2]+nums[i],dp[i-1])

1）偷i，那么就不能偷i-1，为了尽可能多偷会选择隔一个房子偷，也就是偷i-2

2）不偷i，那么就只考虑[0,i-1]

2 打家劫舍

题干

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例 1：
输入：[1,2,3,1]
输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：
输入：[2,7,9,3,1]
输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路

（1）dp[i] 表示考虑[0,i]的房屋的最大金额

（2）递推

dp[i]=max(dp[i-2]+nums[i],dp[i-1])

1）偷i，那么就不能偷i-1，为了尽可能多偷会选择隔一个房子偷，也就是偷i-2

2）不偷i，那么就只考虑[0,i-1]

（3）初始化

dp[0]=nums[0]

dp[1]=max(nums[0],nums[1])

（4）遍历

i从小到大遍历

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

3 打家劫舍II

题干

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的

思路

第一个房屋和最后一个房屋不可以同时偷，所以有两种情况，

一种是明确不偷第一个，只在[1,nums.size()-1]里面偷；一种是明确不偷最后一个，只在[0 ,nums.size()-2]里面偷

（当然可以既不偷第一个又不偷最后一个，但是已经被上面两种情况涵盖了）

两种情况分别用打家劫舍做，为了防止重复代码，所以封装成函数

（1）dp[i] 表示考虑[0,i]的房屋的最大金额

（2）递推

dp[i]=max(dp[i-1],dp[i-2]+nums[i]);

（3）初始化

dp[start]=nums[start];
dp[start+1]=max(nums[start],nums[start+1]);

（4）遍历

从小到大

class Solution {
public:
    int f(vector<int>& nums,int start,int end){
        if(start==end)return nums[start];
        if(start==end-1)return max(nums[start],nums[end]);
        if(start>end)return 0;
        vector<int>dp(nums.size(),0);
        dp[start]=nums[start];
        dp[start+1]=max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[end];
    }
    int rob(vector<int>& nums) {
        if(nums.size()==0)return 0;
        if(nums.size()==1)return nums[0];
        int res1=f(nums,0,nums.size()-2);
        int res2=f(nums,1,nums.size()-1);
        return max(res1,res2);
    }
};

4 打家劫舍III （树形dp）

题干

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

思路

（1）首先确定遍历次序

使用后序遍历（左右中）

1）原因：因为通过递归函数的返回值来做计算。所以先递归调用后计算，左右儿子的结果在求node的结果的时候能用上

2）如果要偷node就不可以偷他的左右儿子，而是考虑从左儿子的左右儿子，右儿子的左右儿子往下偷；如果不偷node就从他的左右儿子开始向下考虑

（2）暴力深度优先搜索+记忆化搜索

f(node) 表示考虑以node为根的子树，能偷的最大金额

1）如果偷node

结果是 node->val+f(node->left->right)+f(node->left->left)+f(node->right->right)+f(node->right->left) （跳过node的左右儿子）

2）如果不偷node

结果是 f(node->left)+f(node->right)

3）记忆化：

结果存到mapping，每层递归都检查node是否有结果，如果有，那么就直接返回结果避免重复计算

class Solution {
public:
    unordered_map<TreeNode*,int>mapping;
    int f(TreeNode*node){
        if(node==NULL)return 0;
        if(node->left==NULL && node->right==NULL)return node->val;
        if(mapping[node])return mapping[node];
        int res1=f(node->left)+f(node->right);
        int res2=node->val;
        if(node->left) res2+=f(node->left->right)+f(node->left->left);
        if(node->right) res2+=f(node->right->right)+f(node->right->left);
        int res=max(res1,res2);
        mapping[node]=res;
        return res;
    }
    int rob(TreeNode* root) {
        return f(root);
    }
};

（3）动态规划（树形dp）

1）f(node) 表示考虑以node为根的子树，返回一个长度为2的数组，f(node)[0]表示偷node的最大金额，f(node)[1]表示不偷node的最大金额

2）终止条件

遇到NULL，返回{0,0}

3）遍历顺序：后序遍历，因为要用到递归函数返回结果来计算这一层

4）单层递归

f(node)[0]=node->val+f(node->left)[1]+f(node->right)[1]

f(node)[1]=max(f(node->left)[0],f(node->left)[1])+max(f(node->right)[0],f(node->right)[1])

<1>偷node：那么左右儿子就不可以偷，用以左儿子为根的子树中不偷左儿子的最大结果，加上，以右儿子为根的子树中不偷右儿子的最大结果，再加上node

<2>不偷node：那么左右儿子就可以偷也可以不偷，左子树的结果取偷左儿子和不偷左儿子的大者，右子树的结果取偷右儿子和不偷右儿子的大者

class Solution {
public:
    vector<int> f(TreeNode* node){
        vector<int>ans_node(2,0);
        if(node==NULL)return ans_node;
        vector<int>l=f(node->left);
        vector<int>r=f(node->right);
        ans_node[0]=node->val+l[1]+r[1];
        ans_node[1]=max(l[0],l[1])+max(r[0],r[1]);
        return ans_node;
    }
    int rob(TreeNode* root) {
        vector<int>res=f(root);
        return max(res[0],res[1]);
    }
};

四股票问题

1 买卖股票的最佳时机

题干

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

思路

（1）贪心

只买卖一次，取最左最小值，取最右最大值

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low = INT_MAX;
        int result = 0;
        for (int i = 0; i < prices.size(); i++) {
            low = min(low, prices[i]);  // 取最左最小价格
            result = max(result, prices[i] - low); // 直接取最大区间利润
        }
        return result;
    }
};

（2）动态规划

1）dp[i][0]第i天不持有股票的情况下，最大的现金量

dp[i][1] 第i天不持有股票的情况下，最大的现金量

2）递推

<1> 在第i天不持有股票

前一天就不持有，或者前一天持有第i天卖掉

dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])

<2> 在第i天不持有股票

前一天就持有

或者之前都不持有第i天买

（注意：不是第i-1天不持有，因为股票只能买一次，只有之前从来没有持有过才可以买）

dp[i][1]=max(dp[i-1][1],-1*prices[i])

3）初始化

dp[0][0]=0：表示第0天不买股票

dp[0][1]=-prices[0]：表示第0天买股票

4）遍历：从小到大遍历天数

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==1)return 0;
        vector<vector<int>>dp(prices.size(),vector<int>(2,0));
        dp[0][0]=0;
        dp[0][1]=-1*prices[0];
        for(int i=1;i<prices.size();i++){
            dp[i][0]=max(dp[i-1][0],prices[i]+dp[i-1][1]);
            dp[i][1]=max(dp[i-1][1],-prices[i]);
        }

        return dp[prices.size()-1][0];
    }
};

2 买卖股票的最佳时机II

题干

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3

思路

（1）贪心

因为不限制买卖次数，所以第i天买入，第j天卖出的收益都可以相当于每天各自买卖一次的收益之和

因此，只要单日利润是正的，就买卖一次，加起来

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res=0;
        for(int i=0;i<prices.size()-1;i++){
            if(prices[i]<prices[i+1]){
                res+=(prices[i+1]-prices[i]);
            }
        }
        return res;
    }
};

（2）动态规划

1）dp[i][0]第i天不持有股票的情况下，最大的现金量

dp[i][1] 第i天不持有股票的情况下，最大的现金量

2）递推

<1> 在第i天不持有股票

前一天就不持有，或者前一天持有第i天卖掉

dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])

<2> 在第i天不持有股票

前一天就持有，或者前一天不持有第i天买

dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])

3）初始化

dp[0][0]=0：表示第0天不买股票

dp[0][1]=-prices[0]：表示第0天买股票

4）遍历：从小到大遍历天数

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

3 买卖股票的最佳时机III

题干

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为0。
示例 4：
输入：prices = [1] 输出：0

提示：

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5

思路

（1）dp[i][j][k]：第i天的最大现金量

j=0表示现在不持有 j=1 表示现在持有

k=0 表示从未持有，k=1表示已经买入一次，k=2表示已经买入2次

（事实上，j=1 k=0是不存在的，也可以用dp[i][j]表示，j=0 表示从未持有，j=1表示第一次购买并持有，j=2表示第一次购买并不持有（已经卖了），j=3表示第2次购买并持有，j=4表示第2次购买并不持有（已经卖了）

（2）递推

<1> 在第i天从未持有

只能是前一天就从未持有dp[i][0][0]=dp[i-1][0][0];

<2> 在第i天第一次购买并持有

前一天就第一次购买并持有，或者前一天从未持有第i天第一次购买买

dp[i][0][1]=max(dp[i-1][0][1],dp[i-1][1][1]+prices[i]);

<3> 在第i天第一次购买并不持有（已经卖了）

前一天就第一次购买并不持有（已经卖了），或者前一天第一次购买并持有第i天卖掉

dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])

<4> 在第i天第2次购买并持有

前一天就就第2次购买并持有，或者前一天就第一次购买并不持有（已经卖了）第i天买

dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])

<5> 在第i天第2次购买并不持有（已经卖了）

前一天就第2次购买并不持有（已经卖了），或者前一天第2次购买并持有第i天卖掉

dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])

3）初始化

dp[0][0][0]=0：表示第0天不买股票

dp[0][1][1]=-prices[0]：表示第0天买股票

dp[0][0][1]=0：表示第0天先买股票，再卖出

dp[0][1][2]=-prices[0]：表示第0天先买股票，再卖出，再买

dp[0][0][2]=-prices[0]：表示第0天先买股票，再卖出，再买，再卖

4）遍历：从小到大遍历天数

最户结果是dp[prices.size()-1][0][2]

最后股票卖出去一定比持有有更多现金，如果dp[prices.size()-1][0][1]最大，那么再最后一天再买卖一次，就有dp[prices.size()-1][0][2]=dp[prices.size()-1][0][1]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<vector<int>>>dp(prices.size(),vector<vector<int>>(2,vector<int>(3,0)));
        
        dp[0][0][0]=0;
        dp[0][1][1]=-1*prices[0];
        dp[0][1][2]=-1*prices[0];
        for(int i=1;i<prices.size();i++){
            dp[i][0][0]=dp[i-1][0][0];
            dp[i][0][1]=max(dp[i-1][0][1],dp[i-1][1][1]+prices[i]);
            dp[i][0][2]=max(dp[i-1][0][2],dp[i-1][1][2]+prices[i]);
            dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][0][0]-prices[i]);
            dp[i][1][2]=max(dp[i-1][1][2],dp[i-1][0][1]-prices[i]);
        }
        return max(dp[prices.size()-1][0][1],dp[prices.size()-1][0][2]);
    }
};