knapsack problem

背包问题是一类经典的动态规划问题，它非常灵活，需要仔细琢磨体会，本文先对背包问题的几种常见类型作一个总结，期望可以用一套框架解决背包问题。

不少同学对背包问题还处于朦胧状态，我特意录了一期视频带你学透0-1背包问题！，这里详细介绍了0-1背包的中dp数组的定义，初始化，递推公式，以及遍历顺序。相信结合本篇题解，会对你学习背包有所帮助。

本篇目录：

• 前序
• 01 背包
  • 二维dp数组 01背包
  • 一维dp数组 01背包
• 416.分割等和子集
• 其他语言实现版本（java，python）
• 背包问题完整攻略

背包问题的经典资料当然是：背包九讲。

但说实话，背包九讲对于小白来说确实不太友好，看起来还是有点费劲的，而且都是伪代码理解起来也吃力。

对于面试的话，其实掌握01背包，和完全背包，就够用了，最多可以再来一个多重背包。

如果这几种背包，分不清，我这里画了一个图，如下：

至于背包九讲其其他背包，面试几乎不会问，都是竞赛级别的了，leetcode上连多重背包的题目都没有，所以题库也告诉我们，01背包和完全背包就够用了。

而完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。

所以背包问题的理论基础重中之重是01背包，一定要理解透！

leetcode上没有纯01背包的问题，都是01背包应用方面的题目，也就是需要转化为01背包问题。

所以我先通过纯01背包问题，把01背包原理讲清楚，后续再讲解leetcode题目的时候，重点就是讲解如何转化为01背包问题了。

之前可能有些录友已经可以熟练写出背包了，但只要把这个文章仔细看完，相信你会意外收获！

01 背包

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

这是标准的背包问题，以至于很多同学看了这个自然就会想到背包，甚至都不知道暴力的解法应该怎么解了。

这样其实是没有从底向上去思考，而是习惯性想到了背包，那么暴力的解法应该是怎么样的呢？

每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n)，这里的n表示物品数量。

所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！

在下面的讲解中，我举一个例子：

背包最大重量为4。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

以下讲解和图示中出现的数字都是以这个例子为例。

二维dp数组01背包

依然动规五部曲分析一波。

1. 确定dp数组以及下标的含义

对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

只看这个二维数组的定义，大家一定会有点懵，看下面这个图：

要时刻记着这个dp数组的含义，下面的一些步骤都围绕这dp数组的含义进行的，如果哪里看懵了，就来回顾一下i代表什么，j又代表什么。

1. 确定递推公式

再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

那么可以有两个方向推出来dp[i][j]，

• 由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]
• 由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

1. dp数组如何初始化

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。如图：

在看其他情况。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

代码如下：

// 正序遍历
for (int j = weight[0]; j <= bagWeight; j++) {
    dp[0][j] = value[0];
}

此时dp数组初始化情况如图所示：

dp[0][j] 和 dp[i][0] 都已经初始化了，那么其他下标应该初始化多少呢？

dp[i][j]在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，因为0就是最小的了，不会影响取最大价值的结果。

如果题目给的价值有负数，那么非0下标就要初始化为负无穷了。例如：一个物品的价值是-2，但对应的位置依然初始化为0，那么取最大值的时候，就会取0而不是-2了，所以要初始化为负无穷。

而背包问题的物品价值都是正整数，所以初始化为0，就可以了。

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

如图：

最后初始化代码如下：

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

费了这么大的功夫，才把如何初始化讲清楚，相信不少同学平时初始化dp数组是凭感觉来的，但有时候感觉是不靠谱的。

1. 确定遍历顺序

在如下图中，可以看出，有两个遍历的维度：物品与背包重量

那么问题来了，先遍历 物品还是先遍历背包重量呢？

其实都可以！！ 但是先遍历物品更好理解。

那么我先给出先遍历物品，然后遍历背包重量的代码。

// weight数组的大小 就是物品个数
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]; // 这个是为了展现dp数组里元素的变化
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

先遍历背包，再遍历物品，也是可以的！（注意我这里使用的二维dp数组）

例如这样：

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        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]);
    }
}

为什么也是可以的呢？

要理解递归的本质和递推的方向。

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。

dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向（包括正左和正上两个方向），那么先遍历物品，再遍历背包的过程如图所示：

再来看看先遍历背包，再遍历物品呢，如图：

大家可以看出，虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上角，根本不影响dp[i][j]公式的推导！

但先遍历物品再遍历背包这个顺序更好理解。

其实背包问题里，两个for循环的先后循序是非常有讲究的，理解遍历顺序其实比理解推导公式难多了。

1. 举例推导dp数组

来看一下对应的dp数组的数值，如图：

最终结果就是dp[2][4]。

建议大家此时自己在纸上推导一遍，看看dp数组里每一个数值是不是这样的。

做动态规划的题目，最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下，然后在动手写代码！

很多同学做dp题目，遇到各种问题，然后凭感觉东改改西改改，怎么改都不对，或者稀里糊涂就改过了。

主要就是自己没有动手推导一下dp数组的演变过程，如果推导明白了，代码写出来就算有问题，只要把dp数组打印出来，对比一下和自己推导的有什么差异，很快就可以发现问题了。

完整C++测试代码

#include <vector>
#include <iostream>

using namespace std;

void test_2_wei_bag_problem1() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    vector<vector<int>> dp(weight.size() + 1, 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]);
        }
    }
    cout << dp[weight.size() - 1][bagWeight] << endl;
}

int main() {
    test_2_wei_bag_problem1();
}

01背包二维dp数组总结

讲了这么多才刚刚把二维dp的01背包讲完，这里大家其实可以发现最简单的是推导公式了，推导公式估计看一遍就记下来了，但难就难在如何初始化和遍历顺序上。

可能有的同学并没有注意到初始化 和 遍历顺序的重要性，我们后面做力扣上背包面试题目的时候，大家就会感受出来了。

下一篇 还是理论基础，我们再来讲一维dp数组实现的01背包（滚动数组），分析一下和二维有什么区别，在初始化和遍历顺序上又有什么差异，敬请期待！

今天我们就来说一说滚动数组，其实在前面的题目中我们已经用到过滚动数组了，就是把二维dp降为一维dp，一些录友当时还表示比较困惑。

那么我们通过01背包，来彻底讲一讲滚动数组！

接下来还是用如下这个例子来进行讲解

背包最大重量为4。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

一维dp数组（滚动数组）

对于背包问题其实状态都是可以压缩的。

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

读到这里估计大家都忘了 dp[i][j]里的i和j表达的是什么了，i是物品，j是背包容量。

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

一定要时刻记住这里i和j的含义，要不然很容易看懵了。

动规五部曲分析如下：

1. 确定dp数组的定义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

1. 一维dp数组的递推公式

dp[j]为 容量为j的背包所背的最大价值，那么如何推导dp[j]呢？

dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。

dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）

此时dp[j]有两个选择，一个是取自己dp[j]，一个是取dp[j - weight[i]] + value[i]，指定是取最大的，毕竟是求最大价值，

所以递归公式为：

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

可以看出相对于二维dp数组的写法，就是把dp[i][j]中i的维度去掉了。

1. 一维dp数组如何初始化

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？

看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

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

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

1. 一维dp数组遍历顺序

代码如下：

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

为什么呢？

倒叙遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

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

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

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

为什么倒叙遍历，就可以保证物品只放入一次呢？

倒叙就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

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

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

那么问题又来了，为什么二维dp数组历的时候不用倒叙呢？

因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！

（如何这里读不懂，大家就要动手试一试了，空想还是不靠谱的，实践出真知！）

再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？

不可以！

因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

（这里如果读不懂，就在回想一下dp[j]的定义，或者就把两个for循环顺序颠倒一下试试！）

所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的！，这一点大家一定要注意。

1. 举例推导dp数组

一维dp，分别用物品0，物品1，物品2 来遍历背包，最终得到结果如下：

一维dp01背包完整C++测试代码

void test_1_wei_bag_problem() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

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

int main() {
    test_1_wei_bag_problem();
}

可以看出，一维dp 的01背包，要比二维简洁的多！ 初始化 和 遍历顺序相对简单了。

所以我倾向于使用一维dp数组的写法，比较直观简洁，而且空间复杂度还降了一个数量级！

在后面背包问题的讲解中，我都直接使用一维dp数组来进行推导。

01背包一维dp数组总结

以上的讲解可以开发一道面试题目（毕竟力扣上没原题）。

就是本文中的题目，要求先实现一个纯二维的01背包，如果写出来了，然后再问为什么两个for循环的嵌套顺序这么写？反过来写行不行？再讲一讲初始化的逻辑。

然后要求实现一个一维数组的01背包，最后再问，一维数组的01背包，两个for循环的顺序反过来写行不行？为什么？

注意以上问题都是在候选人把代码写出来的情况下才问的。

就是纯01背包的题目，都不用考01背包应用类的题目就可以看出候选人对算法的理解程度了。

相信大家读完这篇文章，应该对以上问题都有了答案！

此时01背包理论基础就讲完了，我用了两篇文章把01背包的dp数组定义、递推公式、初始化、遍历顺序从二维数组到一维数组统统深度剖析了一遍，没有放过任何难点。

大家可以发现其实信息量还是挺大的。

如果把动态规划：关于01背包问题，你该了解这些！和本篇的内容都理解了，后面我们在做01背包的题目，就会发现非常简单了。

不用再凭感觉或者记忆去写背包，而是有自己的思考，了解其本质，代码的方方面面都在自己的掌控之中。

即使代码没有通过，也会有自己的逻辑去debug，这样就思维清晰了。常见背包问题可分为：

01 背包问题：

最基本的背包问题就是 01 背包问题：一共有 N 件物品，第 i（i 从 1 开始）件物品的重量为 w[i]，价值为 v[i]。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？

完全背包问题：

完全背包与 01 背包不同就是每种物品可以有无限多个：一共有 N 种物品，每种物品有无限多个，第 i（i 从 1 开始）种物品的重量为 w[i]，价值为 v[i]。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？
可见 01 背包问题与完全背包问题主要区别就是物品是否可以重复选取。

背包问题具备的特征：

是否可以根据一个 target（直接给出或间接求出），target 可以是数字也可以是字符串，再给定一个数组 arrs，问：能否使用 arrs 中的元素做各种排列组合得到 target。

背包问题解法：

01 背包问题：

如果是 01 背包，即数组中的元素不可重复使用，外循环遍历 arrs，内循环遍历 target，且内循环倒序:

完全背包问题：

（1）如果是完全背包，即数组中的元素可重复使用并且不考虑元素之间顺序，arrs 放在外循环（保证 arrs 按顺序），target在内循环。且内循环正序。
（2）如果组合问题需考虑元素之间的顺序，需将 target 放在外循环，将 arrs 放在内循环，且内循环正序。

例题：

01 背包问题

416. 分割等和子集

本题要求把数组分成两个等和的子集，相当于找到一个子集，其和为 sum / 2，这个 sum / 2 就是 target（target 间接给出）。
于是转化为是否可以用 nums 中的数组合和成 target，01 背包问题，外层循环为选择池 num: nums，内层循环为 target。

dp[i] 表示是否存在和为 i 的 num 组合。

• 外层遍历 nums 每个 num；
• 内层遍历 target（由大到小）。

对于元素之和等于 i - num 的每一种组合，在最后添加 num 之后即可得到一个元素之和等于 i 的组合，因此dp[i] 依赖于 dp[i - num]，并且在计算 dp[i - num] 时，要保证索引较小的元素值不被覆盖，需要后向更新 dp[i]，并且当 i - num < i 时， dp[i] 已经更新过，于是：
dp[i] = dp[i] || dp[i - num]
对于特例：如果 sum 为奇数，那一定找不到符合要求的子集，返回 False。
对于边界条件，我们定义 dp[0] = true 表示当 i - num = 0，存在一个 num 和为 i。
最后返回 dp[target]。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int len = nums.size();
        int sum = 0;
        for (int num: nums) {
            sum += num;
        }
        if ((sum & 1) == 1) {
            return false;
        }

        int target = sum / 2;
        vector<bool> dp(target + 1);
        dp[0] = true;

        for(int num: nums){
            for(int i = target; i >= num; i--){

                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];

    }
};

复杂度分析：

• 时间复杂度：O(target × n)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(target)。

494. 目标和

我们想要的 S = 正数和 - 负数和 = x - y
而已知 x 与 y 的和是数组总和：x + y = sum
可以求出 x = (S + sum) / 2 = target
也就是我们要从 nums 数组里选出几个数，令其和为 target（target 间接给出）。
于是转化为是否可以用 nums 中的数组合和成 target，01 背包问题，外层循环为选择池 nums，内层循环为 target。
dp[i] 表示和为 i 的 num 组合有 dp[i] 种。

• 外层遍历 nums 每个 num；
• 内层遍历 target（由大到小）。

对于元素之和等于 i - num 的每一种排列，在最后添加 num 之后即可得到一个元素之和等于 i 的排列，因此在计算 dp[i] 时，应该计算所有的 dp[i − num] 之和。
dp[i] = dp[i] + dp[i - num]
对于边界条件，我们定义 dp[0] = 1 表示只有当不选取任何元素时，元素之和才为 0，因此只有 1 种方案。
最后返回 dp[target]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for(int num : nums) sum += num;
        if(S > sum || (S + sum) % 2 == 1) return 0;
        int target = (S + sum) / 2;
        vector<int> dp(target + 1);
        dp[0] = 1;
        for(int num : nums){
            for(int i = target; i >= num; i--){               
                dp[i] = dp[i] + dp[i - num];
            }
        }
        return dp[target];
    }
};

复杂度分析：

• 时间复杂度：O(target × n)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(target)。

完全背包问题

139. 单词拆分

转化为是否可以用 wordDict 中的词组合成 s，完全背包问题，并且为“考虑排列顺序的完全背包问题”，外层循环为 target ，内层循环为选择池 wordDict。
dp[i] 表示以 i 结尾的字符串是否可以被 wordDict 中组合而成。

• 外层遍历 s 中每一个与 word 同长度的字串 s.substr(i - sz, sz) ；
• 内层遍历 wordDict 每个 word。

判断 s.substr(i - sz, sz) == word：
（1）若不相等，说明与该 word 不匹配，继续遍历；
（2）若相等，说明从 [i - sz] 到 i 的字符与 word 匹配。
dp[i] = dp[i] || d[[i - sz]]
对于边界条件，我们定义 dp[0] = true 表示空串且合法。
最后返回 dp[s.size()]

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size() + 1);
        dp[0] = true;
        for(int i = 1; i <= s.size(); i++){
            for(auto& word: wordDict){
                int sz = word.size();        
                if (i - sz >= 0 && s.substr(i - sz, sz) == word)
                    dp[i] = dp[i] || dp[i - sz];            
            }       
        }
        return dp[s.size()];
    }   
};

复杂度分析

• 时间复杂度：O(target × n)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(target)。

279. 完全平方数
我们想要的 S = 若干个完全平方数的和
完全平方数最小为 1，最大为 sqrt(n)
也就是我们要从 nums = [1, 2, …, sqrt(n)] 数组里选出几个数，令其平方和为 target = n。
于是转化为是否可以用 nums 中的数组合和成 target，完全背包问题，外层循环为选择池 nums，内层循环为 target。
dp[i] 表示和为 i 的 nums 组合中完全平方数最少有 dp[i] 个。

• 外层遍历 nums 每个 num；
• 内层遍历 n。

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, INT_MAX);;

        dp[0]=0;
        for(int num = 1; num <= sqrt(n); num++){
            for(int i = 0; i <= n; i++){
                if(i >= num * num)
                    dp[i] = min(dp[i], dp[i - num * num] + 1);
            }
        }
        return dp[n];
    }
};

对于元素之和等于 i - num * num 的每一种组合，在最后添加 num 之后即可得到一个元素平方和等于 i 的组合，因此在计算 dp[i] 时，应该计算所有的 dp[i − num * num] + 1 中的最小值。
dp[i] = min(dp[i], dp[i - num * num] + 1)
对于边界条件，我们定义 dp[0] = 0。
最后返回 dp[n]

复杂度分析

• 时间复杂度：O(n x sqrt{n})，在主步骤中，我们有一个嵌套循环，其中外部循环是 n 次迭代，而内部循环最多需要 sqrt{n} 迭代。
• 空间复杂度：O(n)，使用了一个一维数组 dp。

322. 零钱兑换

转化为是否可以用 coins 中的数组合和成 amount，完全背包问题，并且为“不考虑排列顺序的完全背包问题”，外层循环为选择池 coins，内层循环为 amount。
dp[i] 表示和为 i 的 coin 组合中硬币最少有 dp[i] 个。

• 外层遍历 coins 每个 coin；
• 内层遍历 amount。

对于元素之和等于 i - coin 的每一种组合，在最后添加 coin 之后即可得到一个元素之和等于 i 的组合，因此在计算 dp[i] 时，应该计算所有的 dp[i − coin] + 1 中的最小值。
dp[i] = min(dp[i], dp[i - coin] + 1)
对于边界条件，我们定义 dp[0] = 0。
最后返回 dp[amount]

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

        }                        
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

复杂度分析：

• 时间复杂度：O(amount x n)，其中 n 为 coins 大小
• 空间复杂度：O(amount)

377. 组合总和 Ⅳ

转化为是否可以用 nums 中的数组合和成 target，完全背包问题，并且为“考虑排列顺序的完全背包问题”，外层循环为 target ，内层循环为选择池 nums。
dp[i] 表示和为 i 的 num 组合有 dp[i] 种。

• 外层遍历 target；
• 内层遍历 nums 每个 num。

对于元素之和等于 i - num 的每一种排列，在最后添加 num 之后即可得到一个元素之和等于 i 的排列，因此在计算 dp[i] 时，应该计算所有的 dp[i − num] 之和。
dp[i] = dp[i] + dp[i - num]
对于边界条件，我们定义 dp[0] = 1 表示只有当不选取任何元素时，元素之和才为 0，因此只有 1 种方案。
最后返回 dp[target]

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

复杂度分析：

• 时间复杂度：O(target x n)，其中 n 为 wordDict 大小
• 空间复杂度：O(target)

518. 零钱兑换 II
转化为是否可以用 coins 中的数组合和成 amount，完全背包问题，并且为“不考虑排列顺序的完全背包问题”，外层循环为选择池 coins，内层循环为 amount。
dp[i] 表示和为 i 的 coin 组合有 dp[i] 种。

• 外层遍历 coins 每个 coin；
• 内层遍历 amount。

对于元素之和等于 i - coin 的每一种组合，在最后添加 coin 之后即可得到一个元素之和等于 i 的组合，因此在计算 dp[i] 时，应该计算所有的 dp[i − coin] 之和。
dp[i] = dp[i] + dp[i - coin]
对于边界条件，我们定义 dp[0] = 1，表示只有当不选取任何元素时，元素之和才为 0，因此只有 1 种方案。
最后返回 dp[amount]。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for(int& coin: coins){
            for(int i = 0; i <= amount; i++){

                if(coin <= i)
                    dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};

复杂度分析：

• 时间复杂度：O(amount x n)，其中 n 为 coins 大小
• 空间复杂度：O(amount)