# 组合总和 IV
题目链接🔗
题目提到顺序不同的序列被视作不同的组合。，所以不是在求组合而是在求排列。
- 确定 dp 数组以及下标的含义
dp [i]: 凑成目标正整数为 i 的排列个数为 dp [i]。
- 确定递推公式
dp [i] 可以由 dp [i-nums [j]] 推导出来，因此递推公式为：$$dp [i] += dp [i-nums [j]]$$
- dp 数组如何初始化
因为递推公式的原因，dp [0] = 1 才能让其他 dp [i] 有数值基础，其他下标初始化为 0。
- 确定遍历顺序
要求的是排列数，因此外层遍历背包，内层遍历物品，内层从前向后遍历。
- 举例推导 dp 数组。
class Solution { | |
public: | |
int combinationSum4(vector<int>& nums, int target) { | |
vector<int> dp(target + 1, 0); | |
dp[0] = 1; | |
for (int i = 0; i <= target; i++) { // 遍历背包 | |
for (int j = 0; j < nums.size(); j++) { // 遍历物品 | |
if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) { | |
dp[i] += dp[i - nums[j]]; | |
} | |
} | |
} | |
return dp[target]; | |
} | |
}; |
# 爬楼梯（进阶）
题目链接🔗
之前的爬楼梯问题最多只能爬两个台阶，现在是 n 个台阶，最多可以爬 n-1 个台阶。
这样就是第一个完全背包问题。每次爬的楼梯数是物品，总台阶数就是背包。
- 确定 dp 数组以及下标含义
dp [i]: 爬到第 i 个台阶，有 dp [i] 种方法。
- 确定递推公式
本题 dp 来源于 dp [i-1],dp [i-2]... 即 dp [i-j]，因此递推公式为：$$dp [i] += dp [i-j]$$
- dp 数组如何初始化
dp [0] = 1，其他下标初始化为 0.
- 确定遍历顺序
本题是求排列数，先爬 1 个台阶再爬 2 个台阶和先爬两个台阶再爬 1 个台阶是不一样的。
因此先遍历背包，再遍历物品。
#include <iostream> | |
#include <vector> | |
using namespace std; | |
int main() { | |
int n, m; | |
while (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++) { // 遍历物品 | |
if (i - j >= 0) dp[i] += dp[i - j]; | |
} | |
} | |
cout << dp[n] << endl; | |
} | |
} |
# 零钱兑换
题目链接🔗
本题和之前的零钱兑换不同，要求凑成的最少硬币数。
- 确定 dp 数组以及下标的含义
dp [j]: 凑成总额 j 的最少硬币数为 dp [j]。
- 确定递推公式
凑足总额为 j - coins [i] 的最少个数为 dp [j - coins [i]]，那么只需要加上一个钱币 coins [i] 即 dp [j - coins [i]] + 1 就是 dp [j]。
所以 dp [j] 要取所有 dp [j - coins [i]] + 1 中最小的。递推公式：$$dp [j] = min (dp [j - coins [i]] + 1, dp [j])$$
- dp 数组如何初始化
首先凑足总金额为 0 所需钱币的个数一定是 0，那么 dp [0] = 0;
考虑到递推公式的特性，dp [j] 必须初始化为一个最大的数，否则就会在递推的过程中被初始值覆盖。
所以下标非 0 的元素都是应该是最大值。
- 确定遍历顺序
本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。
所以遍历顺序两种都可以。
- 举例推导 dp 数组
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 - coins [i]] 是初始值则跳过 | |
dp[j] = min(dp[j - coins[i]] + 1, dp[j]); | |
} | |
} | |
} | |
if (dp[amount] == INT_MAX) return -1; | |
return dp[amount]; | |
} | |
}; |
# 完全平方数
题目链接🔗
转化为背包问题就是，完全平方数就是物品（可以无限件使用），正整数 n 就是背包，求凑满这个背包最少有多少物品。
- 确定 dp 数组以及下标含义
dp [j]: 和为 j 的完全平方数的最少数量为 dp [j]。
- 确定递推公式
dp [j] 可以由 dp [j - ii] 推出，所以递推公式为：$$dp [j] = min (dp [j - ii]+1, dp[j])$$
- dp 数组如何初始化
dp [0] 表示和为 0 的完全平方数最小数量，所以 dp [0] = 0。
其他非 0 下标的 dp [j] 要初始为最大值，这样 dp [j] 在递推的时候才不会被初始值覆盖。
- 确定遍历顺序
因为求的是最少个数，因此遍历顺序不影响结果。
- 举例推导 dp 数组
class Solution { | |
public: | |
int numSquares(int n) { | |
vector<int> dp(n + 1, INT_MAX); | |
dp[0] = 0; | |
for (int i = 1; i * i <= n; i++) { // 遍历物品 | |
for (int j = i * i; j <= n; j++) { // 遍历背包 | |
dp[j] = min(dp[j - i * i] + 1, dp[j]); | |
} | |
} | |
return dp[n]; | |
} | |
}; |
