约克夏犬

背包问题

参考：代码随想录

¶一、01背包

¶楔子

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

一个例子如下：（背包最大容量 4 ）

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

¶🔹 二维dp数组01背包

使用二维数组，即 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 得到的最大价值。

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

初始化 ：

如果背包容量 j = 0 ，即 dp[i][0] ，无论是选取哪些物品，背包价值总和一定为 0。
dp[0][j] 为存放编号 0 的物品的时候，各个容量的背包能存放的最大价值。

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];
}

遍历顺序 ：（两个遍历的维度：物品与背包重量）

先遍历物品，再遍历背包重量，还是先遍历背包重量，再遍历物品都是可以的。（没有覆盖问题，所以都可以）

先遍历物品，再遍历背包重量

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

    vector<vector<int>> dp(weight.size(), vector<int>(bagWeight + 1, 0));
    for (int j = weight[0]; j <= bagWeight; j++) {
        dp[0][j] = value[0];
    }
    // 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]);

        }
    }
    cout << dp[weight.size() - 1][bagWeight] << endl;
}

先遍历背包重量，再遍历物品

void test() {
    vector<int> weight = {1, 3, 5};
    vector<int> value = {15, 20, 30};
    int maxWeight = 4;
    vector<vector<int>> dp(weight.size(), vector<int>(maxWeight + 1, 0));
    for (int j = weight[0]; j <= maxWeight; j++) {
        dp[0][j] = value[0];
    }
	// 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]);
        }
    }
    cout << dp[weight.size() - 1][maxWeight] << endl;
}

参考：leetcode-master/背包理论基础01背包-1

¶🔸 一维dp数组01背包（滚动数组）

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

递推公式 ：（有两个方向推出来 d[j] ）

dp[j] 有两个选择，一个是取自己 dp[j] ，一个是取 dp[j - weight[i] + value[i]] ，指定是取最大的，毕竟是求最大价值，所以递归公式：

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

初始化：

dp[j] 表示容量为 j 的背包，所背的物品价值可以最大为 dp[j] ，那么 dp[0] = 0 ，因此背包容量为 0 所背的物品的最大价值就是 0；当 j != 0 时候，为了让 max 函数中， dp[j] 被覆盖，需要让 dp[j] 取最小值即可，如果 dp[j] >= 0 ，所以 j != 0 时， dp[j] = 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]);
    }
}

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

也正是因为倒序遍历，如果背包重量放在上一层，那么每个 dp[j] 就只会放入一个物品，即：背包里只放入了一个物品。

测试代码 ⭐️

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();
}

参考：leetcode-master/背包理论基础01背包-2

¶416. 分割等和子集

Difficulty: 中等

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

示例 1：

1
2
3

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

Solution

// 将 nums 等分，即按照 sum(nums)/2 为背包容量，nums[i]为 weight[i] 和 values[i]
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1) return false;  // 奇数情况返回 false
        int target = sum / 2;
        vector<int> dp(target + 1, 0);
        // 背包物品与物品价值都为 nums[i]
        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }
};

时间复杂度 ： $O(n^2)$

空间复杂度 ： $O(n)$

参考：leetcode-master/0416.分割等和子集

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

Difficulty: 中等

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

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

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

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

示例 1：

输入：stones = [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]，这就是最优值。

示例 2：

1 2	输入：stones = [31,26,33,21,40] 输出：5

示例 3：

1 2	输入：stones = [1,2] 输出：1

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 100

Solution

// 尽量将石头堆分为尽量相同重量的两堆 A B  (A >= B)
// A - B 之差就是结果
class Solution {
public:
    int lastStoneWeightII(vector<int> &stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum / 2;
        vector<int> dp(target + 1);
        for (int i = 0; i < stones.size(); i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] - dp[target];
    }
};

时间复杂度：$O(m * n)$，m 是石头总重量（准确的说是总总量的一半），n 为石头块数
空间复杂度：$O(m)$

参考：leetcode-master/1049.最后一块石头的重量II

¶494. 目标和

Difficulty: 中等

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

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

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

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

示例 1：

输入：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

示例 2：

1 2	输入：nums = [1], target = 1 输出：1

提示：

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

Solution

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (target > sum) return 0;
        if ((target + sum) % 2 == 1) return 0;  // 不可能出现小数，两者和必为偶数
        int x = (target + sum) / 2;
        vector<int> dp(x + 1);
        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]];  // 递推公式
            }
        }
        return dp[x];
    }
};

时间复杂度：$O(m * n)$，n 是正数个数，m 为背包容量
空间复杂度：$O(m)$

参考：leetcode-master/0494.目标和

¶474. 一和零

Difficulty: 中等

请你找出并返回 strs 的最大子集的大小，该子集中最多有 m 个 0 和 n 个 1 。如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

给你一个二进制字符串数组 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 。

示例 2：

1
2
3

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

Solution

// 01 背包问题
// 此时背包容量属性是二维的 类似于一个真正的背包 长 m 宽 n
// 背包物品是 strs 里面的子字符串, 需要统计其 0 1 大小, 看能不能放进背包
// 物品价值都是 1
// dp[i][j] : 最多有i个0和j个1的str的最大子集的大小为 dp[i][j]
// dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (const auto str : strs) {
            int oneNum = 0, zeroNum = 0;
            for (char c : str) {
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

时间复杂度： $O(l* m * n)$，其中 $l$ 为 strs 长度

空间复杂度： $O(m * n)$

参考：leetcode-master/0474.一和零

¶二、完全背包

¶楔子

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

一个例子如下：（背包最大容量 4 ）

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

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]);
    }
}

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

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

注意 🙋‍♂ ：在完全背包中，对于一维dp数组来说，for 循环嵌套顺序无所谓。

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

测试代码如下 ⭐️

// 先遍历物品，在遍历背包
void test_CompletePack() {
    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 = weight[i]; j <= bagWeight; j++) { 	// 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_CompletePack();
}

// 先遍历背包，再遍历物品
void test_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1, 0);
    for(int j = 0; j <= bagWeight; j++) { 			// 遍历背包容量
        for(int i = 0; i < weight.size(); i++) { 	// 遍历物品
            if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_CompletePack();
}

更需要注意 🙋

对于纯完全背包问题，其 for 循环的先后循环是可以颠倒的！但如果题目稍稍有点变化，就会体现在遍历顺序上。

参考：leetcode-master/背包问题理论基础完全背包

¶518. 零钱兑换 Ⅱ

Difficulty: 中等

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

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

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

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

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

1
2
3

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

1 2	输入：amount = 10, coins = [10] 输出：1

提示：

1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000

Solution

// 注意此时的遍历顺序，先遍历物品，后遍历背包重量
// 求取的是组合问题
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        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];
    }
};

时间复杂度： $O(m * n)$，其中 m 为硬币规格数， n 为总金额

空间复杂度： $O(n)$

参考：leetcode-master/0518.零钱兑换II

¶377. 组合总和 Ⅳ

Difficulty: 中等

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

1 2	输入：nums = [9], target = 3 输出：0

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

**进阶：**如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

Solution

// 注意此时的遍历顺序，先遍历背包重量，后遍历物品
// 完全背包问题, 排列问题
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] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]]) 
                    dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

时间复杂度： $O(m * n)$，其中 m 为 nums 长度， n 为目标整数

空间复杂度： $O(n)$

参考：leetcode-master/0377.组合总和Ⅳ

¶70. 爬楼梯

Difficulty: 简单

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

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

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

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

Solution

// 完全背包问题，应该按照排列来求结果，因为 1 2 和 2 1 是两种可能
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        int m = 2;
        // 其中 j : 表示背包重量最大为 n
        for (int j = 1; j <= n; j++) {
            // 其中 i: 表示背包中的物品重量为{ 1 2 ... m }
            for (int i = 1; i <= m; i++) {
                if(j - i >= 0) dp[j] += dp[j - i];
            }
        }
        return dp[n];
    }
};

时间复杂度： $O(m * n)$，其中 m 为每次可以跳跃的最大阶数，此题 m = 2， n 为目标阶数

空间复杂度： $O(n)$

参考：leetcode-master/0070.爬楼梯完全背包版本

¶322. 零钱兑换

Difficulty: 中等

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

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

示例 1：

1
2
3

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1 2	输入：coins = [2], amount = 3 输出：-1

示例 3：

1 2	输入：coins = [1], amount = 0 输出：0

示例 4：

1 2	输入：coins = [1], amount = 1 输出：1

示例 5：

1 2	输入：coins = [1], amount = 2 输出：2

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

Solution

// 完全背包问题
// dp[j]: 凑足总金额为 j 所需钱币的最少个数为 dp[j]
// dp[j] 有两种可能
// 1. 没有任何操作				   --> dp[j]
// 2. dp[j - coins[i]] 获取一个硬币  --> dp[j - coins[i]]
// 递推公式：dp[j] = min(dp[j], dp[j - coins[i]] + 1)

// 初始化 dp[0] = 0, 凑足总金额 0 所需钱币的个数一定是0
// dp[j] = INT_MAX  (j != 0) 因为 min() 函数，需要在递推中避免被初始值覆盖

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);
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

时间复杂度： $O(m * n)$，其中 m 为 coins 长度， n 为目标总金额

空间复杂度： $O(n)$

参考：leetcode-master/0322.零钱兑换

¶279. 完全平方数

Difficulty: 中等

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

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

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

示例 1：

1
2
3

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

示例 2：

1
2
3

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 104

Solution

// 与零钱兑换基本相同
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        // 注意此时遍历先遍历物品, 还是先遍历背包容量都可以
        // 先遍历物品, 后遍历背包容量
        // for (int i = 1; i <= n; i++) {
        //     for (int j = i * i; j <= n; j++) {
        //         dp[j] = min(dp[j], dp[j - i * i] + 1);
        //     }
        // }
        // 先遍历背包容量, 后遍历物品
        for (int j = 1; j <= n; j++) {
            for (int i = 1; i <= n; i++) {
                if (j - i * i >= 0)
                    dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }  
};

时间复杂度： $O(n * \sqrt{n})$，其中 n 为给定的正整数。

空间复杂度： $O(n)$

参考：leetcode-master/0279.完全平方数

¶139. 单词拆分

Difficulty: 中等

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

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

1
2
3

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

示例 2：

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

示例 3：

1 2	输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false

Solution

// 完全背包问题：
// 背包容量: s.size()
// 背包物品: s(i - j) 组成的字符串
// 递推公式:
// dp[j] = true   (dp[i] = true, s(i - j)构成的字符串在字典内部)
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int j = 1; j <= s.size(); j++) {  // 遍历背包容量
            for (int i = 0; i < j; i++) {      // 遍历物品: s(i - j) 组成的字符串
                string word = s.substr(i, j - i);
                if (dict.find(word) != dict.end() && dp[i]) {
                    dp[j] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

时间复杂度：$O(n^3)$，因为 substr 的时间复杂度是 $O(n)$ （n 为 substring 的长度）

空间复杂度：$O(n)$

参考：leetcode-master/0139.单词拆分

¶三、多重背包

¶楔子

有 N 种物品和一个容量为 V 的背包。第i种物品最多有 Mi 件可用，每件耗费的空间是 Ci ，价值是 Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。多重背包和 01背包非常像，只需要将 Mi 摊开，其实就是一个 01背包问题。

一个例子如下：（背包最大容量 10 ）

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

摊开后：

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

如此就转化为 01 背包问题，且每个物品只用一次。

测试程序如下 ⭐️

#include <iostream>
#include <vector>
using namespace std;
void test() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    vector<int> nums = {2, 3, 2};
    int bagWeight = 10;
    // 摊开 nums 
    for (int i = 0; i < nums.size(); i++) {
        while (nums[i] > 1) {
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }
    // 01 背包问题
    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();
}

参考：leetcode-master/背包问题理论基础多重背包

¶四、参考资料

代码随想录
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台