我家自动化

这个屌丝很懒，什么也没留下！

热门标签

二刷力扣——DP算法（背包问题）_背包问题力扣

作者：我家自动化 | 2024-08-22 18:20:45

踩

背包问题力扣

本文截图来自力扣官方题解、评论区其他题解以及代码随想录。

如果某一问题有很多重叠子问题，使用动态规划是最有效的。

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

DP五步曲：

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

70. 爬楼梯

1、省略列出上面的五部。

确定递推公式：

所以递推公式和斐波那契数列一样，但是递归的话会超时，所以遍历推导：

之后确定递推公式，很多都是看第n步之前的第n-1步的情况，然后来分类讨论第n步怎么根据第n-1步的情况得到值。

2、学习新方法：矩阵快速幂。

这里M的构造，使得（f（n+1)，f（n））能够转换成各自都下标减一的向量，这是矩阵的 dp数组。从而把下标较小的那一个向量再转换为M×下标更小的向量，最后会递推成（f（n+1)，f（n））与（ f(1),f(0) ）的关系。

思考题：

一般方法应该是待定系数法把f(x)后面的推出来。

代码如下。

注意求a的n次方的函数matrixPow 。不是计算n次，而是每一次都计算平方，如果是奇数，就需要单独乘一个矩阵。比如5：一开始5&1是1，所以ret=Ea=m；然后a变成了m^2，5右移变成2，if里面不成立，a再平方变成m^4，2右移变成1；if里面成立，结果=ret * a=m * m^4。以后可能还能用到。


class Solution {
public:
    //矩阵乘法
    vector<vector<long long>> multiply(vector<vector<long long>> &a,vector<vector<long long>>& b)
    {
        vector<vector<long long>> c(2, vector<long long>(2));
        for(int i=0;i<2;++i)
        {
            for(int j=0;j<2;++j)
            {
                c[i][j]=a[i][0]*b[0][j]+a[i][1]*b[1][j];
            }
        }
        return c;
    }
 
    vector<vector<long long>> matrixPow(vector<vector<long long>> a,int n)
    {
        vector<vector<long long>> ret = {{1, 0}, {0, 1}};
        while(n>0)
        {
            if((n&1)==1)//是奇数
            {
                ret=multiply(ret,a);
            }
            a=multiply(a,a);//a^2、a^4……
            n >>= 1;    //除2
        }
        return ret;
    }
 
    int climbStairs(int n) {
        vector<vector<long long>> m={{1,1},{1,0}};//m矩阵
        vector<vector<long long>> res=matrixPow(m,n);//求m的n次方
        return res[0][0];
    }
};

时间复杂度：O(logn)

3、还有一种得到通项公式了直接带入 n 求到结果的：

但是对于常微分方程什么的高数知识有些忘记了。

从力扣这篇题解学到了很多东西：

746.最小花费爬楼梯

跟上面一样，dp表示到第i个台阶的最小花费，最后台阶下标是n。

初始化的话：

当i>=2，上一步有可能爬两步，也可能一步，所以递推公式：


class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n+1,0);//到i个台阶的花费
        // dp[0]=0;
        // dp[1]=0;
        for(int i=2;i<=cost.size();++i)
        {
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
};

上述代码的时间复杂度和空间复杂度都是 O(n)。注意到当 i≥2时，dp[i]只和 dp[i−1] 与 dp[i−2] 有关，因此可以使用滚动数组的思想，将空间复杂度优化到 O(1)。


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

以后也会用滚动数组代替dp本身，要先会dp数组的实现了，再实现滚动数组。

62. 不同路径

得是二维dp了，dp[i][j]：(i,j)到终点的路径条数。

因为只能两个方向移动，所以是在(i-1,j)和(i,j-1)的基础上得到（i,j）的。

这里把终点和起点调换了一下，想让遍历顺序从左到右，从上到下而已。（左右和上下的顺序谁在前都可以）

注意初始化了一行+一列。


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

还可以用滚动数组，一维代替二维。只是省略了空间，但是还是两个循环的动态规划，只不过i不参与到值的推导中。


 
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n,0);
       // for(int i=0;i<m;++i)dp[i][0]=1;
        for(int j=0;j<n;++j)dp[j]=1;
        for(int i=1;i<m;++i)
        {
            for(int j=1;j<n;++j)
            {
                dp[j]+=dp[j-1];//只能向上/左
            }
        }
        return dp[n-1];
    }
};

时间复杂度：O(m*n)

空间复杂度：O(n)

也可以省略n这个维度，空间复杂度变O(m)。


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

注意一维的时候，这个参与推导的维度得在内循环，要经历n轮的 dp[0]到dp[m-1] 才能得到最终的dp[m-1]。

63. 不同路径 II

跟上面的区别是遇到障碍的话dp[i][j]直接变0了。

注意初始化的时候遇到障碍物就退出了，障碍物之后的dp都是0.

二维：


class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<m;++i){
            if(obstacleGrid[i][0]==1)break;
            dp[i][0]=1;
        }
        for(int i=0;i<n;++i){
            if(obstacleGrid[0][i]==1)break;
            dp[0][i]=1;
        }
 
        for(int i=1;i<m;++i)
        {
            for(int j=1;j<n;++j)
            {
                if(obstacleGrid[i][j]==1)dp[i][j]=0;
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];//只能向上/左
            }
        }
        return dp[m-1][n-1];
 
 
    }
};

一维：


class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<int> dp(m);
        for(int i=0;i<m;++i){
            if(obstacleGrid[i][0]==1)break;
            dp[i]=1;
        }
 
        for(int j=1;j<n;++j)
        {
            for(int i=0;i<m;++i)
            {
                if(obstacleGrid[i][j]==1)dp[i]=0;//障碍处
                else {        //没有障碍
                    if(i>0)dp[i]+=dp[i-1];//[[0,1],[0,0]]
                }
            }
        }
        return dp[m-1];
    }
};

注意这里一维的话，因为没有给另一个维度的第一行/列初始化，所以这里i 得从0开始。举例可知：[[0,1],[0,0]]

循环体里面分为有障碍和没障碍。必须在二维的基础上来调整，虽然简略但是解释性不是很好。

思想同下。

343. 整数拆分

1、DP

dp[i]：正整数i拆分得到的最大乘积。

可以分成两种情况：①n拆分成2个正整数的和。②n拆分成大于2个正整数的和。

①的话，dp[n]应该=j*(n-j)的最大值，②的话，dp[n]应该等于j*dp[n-j]的最大值。j是从1遍历到i-1，因为dp[n-j]是分解n-j这个数得到的最大的乘积，所以至少分解了2次，乘j就是至少分解了3次。

所以dp[n]应该取两种情况下的最大值,dp[n]=max( j * ( n-j ), j * dp[n-j] )。这个dp[n]只是n包含j的时候分解的最大值（只考虑了右边的最大值），和前面的n包含1……j-1的时候分解的最大值没有联系起来，所以这个式子还是不对的。

因此dp[n]还要和自己比较，和之前的j对应的最大值（也就是最近一次更新的dp[n]比较），最终才是最大值。也就是左边右边都要考虑。


class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1,0);
        dp[2]=1;
        for(int i=3;i<=n;++i)
        {
            int curmax=INT_MIN;
            for(int j=1;j<i;++j)
            {
                curmax=max(curmax,j*max((i-j),dp[i-j]));//在左边是1到i-1的基础上，右边2种情况：仅一个数/再划分。取最大值
            }
            dp[i]=curmax;//确定dp[i]
        }
        return dp[n];
    }
};

2、数学解决：

对于大于 4的正整数，总是存在一种拆分的方案，使得拆分成的两个正整数的乘积大于拆分前的正整数。

力扣题解用导数和归纳证明法证明的。

简单来说是：

因为大于4的整数f，都可以分解为2+f-2，而2(f-2)肯定比f大，所以有大于4的整数，就分解他。所以乘积式子左边只会出现 1、2、3。×1的话会变小所以不考虑，那左边只会有2和3。

2和3的个数怎么确定？答：

所以所有情况就是：若干个3和两个/一个/没有 2。所以把 n求余。余1 是4的倍数，即若干个3和两个2.其他同理。


class Solution {
public:
    int integerBreak(int n) {
     
 
        //数学
        if(n<4)return n-1;
        int mi=n/3;
        int re=n%3;
        if(re==0)
        {
            return pow(3,mi);
        }
        else if(re==1)//2个2
        {
            return pow(3,mi-1)*4;
        }
        return pow(3,mi)*2;//1个2
    }
};

96. 不同的二叉搜索树

恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树：可以遍历每个数字 i，将该数字作为树根，将 1⋯(i−1) 序列作为左子树，将 (i+1)⋯n 序列作为右子树。接着可以按照同样的方式递归构建左子树和右子树。

左子树和右子树的节点数肯定小于n，所以先得到小于n的数量，再从而得到n个节点的数量。典型用动态规划。

dp[i]：恰由 i 个节点组成且节点值从 1 到 i 互不相同的 二叉搜索树 数目。

递推公式：所以以左子树为标准：左子树节点个数可以从1到n-1，其不同搜索树数目为dp[1]——dp[n-1]。那么右子树节点数量就是i-1-左子树节点个数，不同搜索树数目同理。

初始化：dp[1]一个节点的情况也可以由循环得出（i从1 开始）


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=0;j<i;++j)
            {
                dp[i]+=dp[j]*dp[i-j-1];//左子树j个；右子树i-j-1 个
            }
        }
        return dp[n];
    }
};

和上面整数拆分是一样：

要得到每一个dp[i]，还需要一层内循环来统计最大值/总数。不同路径是显式地说明了用两层循环，这两道题是隐式的。

相同点是 dp[i]都由dp[1]——dp[i-1] 和前面几轮的 dp[i]自己 得到，这是一个二维的过程，两个不同路径的二维dp 简化成了一维滚动数组；而这里本身就是一维数组。区别是存储空间的大小，相同的是二维的过程、时间。

开始背包：

46. 携带研究材料（第六期模拟笔试）

dp数组的定义是需要细想的，确定了之后是需要牢记贯穿全题的。

1、定义：

dp[i][j]：从【0,i】范围内随便选材料，使得重量是j，dp[i][j]是最大价值。

所以前一个下标范围是[0,m-1]（假设m个物品），后一个下标范围是[0,n]。假设 n 是背包可承受最大重量/空间.

重量这个维度从0开始，列从第一个物品开始。

2、初始化：

联系实际，重量为0的时候价值肯定也为0，所以第一列是0。

选第一个物品的时候，当这个物品重量比此时的背包重量 j 还要大，那就不能放这个物品，值为0；≤的话可以放。

所以就初始化j>=weights[0] 的情况：


// 初始化
    for(int i=weights[0];i<=n ;++i)dp[0][i]=values[0];

3、递推公式：

得到dp[i][j]有2种情况：

①一定不能放物品 i。如果物品i放进重量为j的背包会超重，那么不能把i放进去，所以重量设定为j的话，从[0,i-1]选择和从[0,i]选择的最大价值是一样，所以 dp[i][j] = dp[i-1][j] 。

②可放可不放物品 i。如果不会超重，可以选择是否放进去。

物品 i 放进去，背包最大重量为 j ，还没有放进去物品 i 的时候，背包的最大重量为 j - weight[i] ，数量为i-1，所以这时背包的最大价值为 dp[ i-1 ][ j - weight[i] ]。加入物品 i ，背包价值 dp[i][j] 就为 dp[ i-1 ][ j - weight[i] ] + value[i] 。

不放进去和前面①一样。

取两者最大值：

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

4、遍历顺序：

观察到dp[ i ]d [ j ] 是由统一左上角的值推来的。所以遍历顺序只要满足在计算dp[ i ]d [ j ] 的时候左上角的值都已经得到了就行。所以先行还是先列都是可以的。


#include<vector>
#include<iostream>
 
using namespace std;
 
int main()
{
    int m,n;
    cin>>m>>n;
    vector<int> weights(m);
    vector<int> values(m);
    for(int i=0;i<m;++i)
    {
        cin>>weights[i];
    }
    for(int i=0;i<m;++i)
    {
        cin>>values[i];
    }
    
    vector<vector<int>> dp(m,vector<int>(n+1,0));//从【0,i】范围内选材料 重量是j的最大价值
    // 初始化
    for(int i=weights[0];i<=n ;++i)dp[0][i]=values[0];
    
    for(int i=1;i<m;++i)
    {
        for(int j=0;j<=n;++j)
        {
            if(j<weights[i])dp[i][j]=dp[i-1][j];//物品i太大一定放不了
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i]]+values[i]);//可放可不放
        }
    }
    cout<< dp[m-1][n]<<endl;
    return 0;
}

同样可以把二维数组转化成一维DP数组来递推：

1、定义

可以发现递推公式dp[i]只出现在左边，dp[i-1]只出现在右边，所以完全可以省略掉这一个维度，只留下上面二维数组的列。

2、这样递推公式变成：


if(j<weight[i] ) dp[j]=dp[j];
else dp[ j ] = max(dp[ j ], dp[ j - weight[ i ] ] + value[ i ]);

那个if 也可以省略了。变成：

dp[j]=max(dp[j],dp[j-weights[i]]+values[i]);

这是递推公式的变化。

3、重量维度必须倒着推。

在一刷的时候解释的比较清楚了：

为什么背包是倒序遍历？倒序遍历是为了保证物品i只被放入一次。比如上面的例题，物品0的重量weight[0] = 1，价值value[0] = 15。第一轮i=0：先算dp[1]=max(dp[1],dp[0]+15)=15，那么dp[2]=max(dp[2] , dp[1] + 15)=30，dp[2]就包含了2个物品0。肯定是错的。那么考虑反过来，先算dp[4]的话，先算dp[4]=max(dp[4],dp[3]+15)=15，dp[3]=max(dp[3],dp[2]+15)=15，没有重复包含。所以只能倒序遍历。所以倒序遍历的原因是，本质上还是一个对二维数组的遍历，只不过第二行的覆盖第一行，第三行的覆盖第二行……并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。从左到右覆盖左边的值就是这一层更新过的了。

为什么只能先物品再背包？还是那句话：一维遍历本质上还是一个对二维数组的遍历，右下角的值依赖上一层左上角的值，所以需要保证左边的值仍然是上一层的，结合上面的背包倒序遍历，想象这个过程中，dp数组倒序遍历一轮就是更新了之前二维数组的一行，然后下一轮就是更新二维数组的下一行，这样左边的值仍然是上一层的。

如下图。既然没有了i，那么进行第二轮的j=4,j=3的时候，之前一轮的这两个值就会被覆盖，只有以“先物品再背包，背包倒序遍历”这个顺序来才能使得dp[j]和二维的dp[i-1][j]是一样的效果，我需要用到的是前一轮的值，那么不能先更新前一轮的值，而是要从后往前更新。所以除了这个情况之外的，都会覆盖原来左上角的值，是不对的。

二维数组的时候，本来就是由上一层的dp[i-1]计算得到的，所以上一层的值直接能拿来用不会被覆盖，所以先物品先背包都可以。

4、初始化。

递推公式只包含j，所以不用初始化第一行。

那么假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。


#include<iostream>
#include<vector>
using namespace std;
 
void maxValue(){
    int m,begweight;//M 代表物品的种类数，begweight是背包容量
    cin>>m>>begweight;
    vector<int> weight(m);
    vector<int> value(m);
    for(int i=0;i<m;++i){
        cin>>weight[i];
    }
    for(int i=0;i<m;++i){
        cin>>value[i];
    }
    vector<int> dp(begweight+1,0);
    //递推
    for(int i=0;i<m;++i){
        for(int j=begweight;j>=weight[i];--j){
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    cout<< dp[begweight] << endl;
}
 
int main(){
    maxValue();
    return 0;
}

根据表格，观察每个元素依赖哪些位置的其他元素得到，从而确定遍历顺序。

416. 分割等和子集

同上面0-1背包的模板。weight数组和values数组都是nums。背包能背sum的一半就对。


class Solution {
public:
    bool canPartition(vector<int>& nums) {
        //背包容量：sum(nums)/2;价值同容量
        int sum=0;
        for(int num:nums)
        {
            sum+=num;
        }
        if(sum%2==1)return false;
        int n=sum/2;
        vector<int> dp(n+1,0);
        for(int i=0;i<nums.size();++i)
        {
            for(int j=n;j>=nums[i];--j)
            {
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[n]==n)return true;
        return false;
    }
};

1049. 最后一块石头的重量 II

和上道题一样

思想：把若干次两个石头相撞，转化成一次两堆石头相撞。

举例：

[2,7,4,1,8,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]，这就是最优值。

总的式子可以表达为：((4-2)-1)+(8-7)+(1-1)+1。最后只剩下1个1，一个减号对应一次相撞。多次相减得到剩下的重量。

式子可以转变成：4+8+1+1-2-1-7。就是把4、8、1分成一堆，其他的是另一堆。一次相撞，就能得到结果。

于是背包容量又是元素总和的一半，尽量装满就行。

最后dp[target] 是最接近一半的一堆，另一堆减去这一堆就是结果。


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

494. 目标和

这里求方案数，不是某个重量对应的包里面的价值

所以定义改为：nums里面随便选num，使得背包里面是j的方法种数。

因为直接二维数组转化成的滚动数组，思考过程还是二维的：第i轮要计算dp[j]，那么上一轮i-1轮的dp[j-nums[i]]还没有更新：含义是从[0,i-1] 选物品，使得背包里面是j-nums[i] 的方法数①。上一轮的dp[j]：含义是从[0,i-1] 选物品，使得背包里面是j 的方法数②。所以第i轮是从[0,i] 选物品，继承了①的，背包里面再放入i物品，根据数学求排列组合那一块的加法乘法原理，选了i 的方法数是①；不选物品i，方法数同②，所以这一轮i 的dp[j] 就是两者加起来，考虑两种情况。

这个公式在后面背包解决排列组合问题的时候还会用到。


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

474. 一和零

建立原始dp数组，应该有3个维度：三个维度分别是字符串、0的容量和 1 的容量。

只是比普通背包多了一个维度。普通背包一个物品维度，一个背包维度；这里有两个背包维度。

所以过程两层循环变成三层循环，为了实现滚动数组，还是物品在外循环，两个背包在内循环。

递推公式：

可见去掉维度k和普通背包一模一样。

那么同样省略物品这个维度，变成滚动数组可以节省空间但时间一样：


class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));    在[0,i]里面选，有i个0和j个1的最大长度
        for(string str:strs){
            int x=0,y=0;
            //统计x和y
            for(char s:str){
                if(s=='0')  x++;
                else y++;
            }
            //二维递推
            for(int i=m;i>=x;--i){
                for(int j=n;j>=y;--j){
                    dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1);
                }
            }
        }
        return dp[m][n];
    }
};

初始化、顺序也是和前面的滚动数组一样的。

518. 零钱兑换 II

1、左右上下顺序：

01背包逆序是为了不重复放入某个物品，因为dp[j]依靠物品 i 这一行左边的值得来，从左往右顺序来的话左边某个值放入了这一行代表的物品i，dp[j]取的是上面递推公式的右边的值，那就会再加一次value[i]，也就是又放入一次物品 i。

所以从左往右不符合01背包要求，但是却是符合完全背包的要求的，因为物品i有无限多个，对于物品i这行，想放几次就放几次，那么肯定从左往右才能得到完全背包的最大值。完全背包的最大值肯定是比01背包的最大值要大，因为完全背包较大的一些物品的价值可以重复放入，总的价值就会增大，所以要想最大，就得采用从左往右这种可以重复取物品的顺序。

2、物品背包内外顺序：

组合问题的话是先物品还是先背包呢，先物品这种情况，是对于某个物品i，来看逐渐增大的背包是否能装下，所以先在逐渐增大的背包里面看1能不能装下，再看2能不能装下，再看5能不能装下，然后结束。所以只会出现顺序为1,2,5的情况，所以上面输出为4的例子中，4个组合分别是(1,1,1,1,1)，（1,1,1,2），(1,2,2)，(5)，物品相对顺序都是1、2、5，所以只考虑一种排列顺序，求出来的就是组合数。

先背包的情况，是对于某个背包j，来看依次每个物品是否能装下，所以先看背包1能不能装下物品1、2、5,再看背包2能不能装下1、2、5，放入物品的这个顺序是1,2,5,1,2,5,1,2,5……，这里对于这三个数所有的排列（1,2,5；1,5,2；2,1,5；2,5,1；5,1,2，5,2,1）都考虑到了，所以求出来的是排列数而不是组合数。

所以这里只能先物品。


class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);//[0,i]里面选，使得容量是j的背包 的硬币组合数
        dp[0]=1;    //啥也不选也是一个组合
        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];
    }
};

377. 组合总和 Ⅳ

说是组合总和，但是

顺序不同的序列被视作不同的组合。

所以其实是求排列数，刚好就是和上一题的物品背包内外顺序相反，其他都一样


class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> 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]<INT_MAX-dp[j-nums[i]]){//dp[j]+dp[j-nums[i]]<INT_MAX
                    dp[j]+=dp[j-nums[i]];
                }
            }
        }
        return dp[target];
    }
};

会转换成01背包/完全背包问题。

322. 零钱兑换

dp[j]的定义根据题目是凑成j所需的最少的硬币个数。

递推公式：还是两种情况，在第i个之前的最少硬币数（不选i）；选上了i个的最少硬币数，这里应该取两者最小值。

遍历顺序：这里是求硬币个数而不是组合/排列种数，所以先物品或者先背包都可以。但是是完全背包，所以物品、背包遍历得从0开始。

初始化：有讲究，之前计算最大值，直接都初始化为0。这里是最小值。dp[0]肯定是=0。但是其他元素不能和之前一样初始化为0，想想之前最大价值初始化为0是为了不在取max的时候覆盖非0值，那么现在应该取INT_MAX，保证比过程中生成的元素值都大，就不会在取min的时候覆盖他们。保证元素能够被更新。

最后如果dp[amount]没有被更新，说明不能凑成amount，所以返回-1。


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

322. 零钱兑换

跟上题一样计算最小值，物品其实是1到根号n这些数，他们的价值是i的平方。


class Solution {
public:
    int numSquares(int n) {
        //物品是1,2,3,……,根号n。
        vector<int> dp(n+1,INT_MAX-1);
        dp[0]=0;
        for(int i=1;i<=sqrt(n);++i){
            for(int j=i*i;j<=n;++j){
                dp[j]=min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
};

139. 单词拆分

感觉说成是背包不太形象。

含义：dp[j]=true：可以利用字典中出现的一个或多个单词可以拼接出子串 [0,j]

普通的动态规划。内循环和外循环都是在字符串s上的。过程也是一维就能表示出来。

外循环i是1到n，意思是检查出子串[0,i]能不能被构成；要得出结论还得构造一个内循环j，因为可以把子串[0,i] 分成[0,j]和[j,i]两部分，[0,j]是dp[j]可以直接用，因为前面已经得到（体现出DP），[j,i]的话还需要自己来检查，是不是wordDict里面的某个单词（查找为了速度，使用Set结构）。找到了一个符合的j 就可以跳出内循环检查下一个子串[o,i+1] 了。

注意初始化dp[0]也是true。遇到第一个符合的单词才能让dp[0]和查找[0,j]都为true。


class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //物品：wordDict。
        //背包容量：s
        vector<bool> dp(s.size()+1,false);  
        dp[0]=true;
        unordered_set<string> wordSet(wordDict.begin(),wordDict.end());
        for(int j=1;j<=s.size();++j){
            for(int i=0;i<=j;++i){
                string sub=s.substr(i,j-i);
                if(wordSet.find(sub)!=wordSet.end() && dp[i]){
                    dp[j]=true;
                    break;//可以
                }
            }
        }
        return dp[s.size()];
    }
};