LC518. 零钱兑换Ⅱ
刚开始一气写成，没想到犯了个那么傻×的毛病
class Solution
{
public:
int change(int amount, vector<int>& coins)
{
int size = coins.size();
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int i = 0; i < size; ++i)
{
int j = 1;
for (; j >= coins[i]; ++j)
{
if (j > amount) break;
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};
int main()
{
Solution solution;
vector<int> coins = {1,2,5};
solution.change(5, coins);
return 0;
}
for表达式的条件语句，应该是作为循环继续或者终止的判断，不能作为循环开始的依据。
咳~~~
int change(int amount, vector<int>& coins)
{
int size = coins.size();
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int i = 0; i < size; ++i)
{
for (int j = coins[i]; j <= amount; ++j)
{
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
LC37. 组合总和Ⅳ
1、dp[i]含义：凑成目标正整数为 i 的排列个数为dp[i]
2、递推公式：dp[j] += dp[j - nums[i]]
3、dp数组初始化：dp[0]初始化为1
4、遍历顺序：
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包（无需考虑元素之间的顺序）
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品（需要考虑元素之间的顺序）
本题还是要从dp数组的含义出发：
例子分析，[1, 2, 3]，target = 4：
分析下排列顺序（背包在循环外层）的红色格子推导：
- 红色格子(i, j) = (1, 3)，dp[3] += dp[2] (2是 j - nums[i]，即3 - 1所得)，即当前物品为1，有dp[2]种刚好装满weight为3的背包
- 红色格子(i, j) = (2, 3)，dp[3] += dp[1] (1是 j - nums[i]，即3 - 2所得)，即当前物品为2，有dp[1]种刚好装满weight为3的背包
- 红色格子(i, j) = (2, 3)，dp[3] += dp[0] (0是 j - nums[i]，即3 - 3所得)，即当前物品为3，有dp[0]种刚好装满weight为3的背包
抽象上述公式，即为dp[3] = dp[0] + dp[1] + dp[2]。
对遍历顺序的理解：对于“求解刚好装满背包的题目”，如“目标和”、“零钱兑换Ⅱ”、“组合总和Ⅳ”，虽然dp递推公式都一致dp[j] += dp[j - nums[i]]。但当
- 物品在循环外层的话，是每个物品分别去询问排着队的不同容量的背包，要不要装下我，装和不装，物品放入背包的顺序和开始物品的相对顺序都不会变。
- 背包在循环外层的话，是每个背包分别去询问排着队物品，还装不装你，而此前背包我是装满装的我不知道，我是知道我现在还剩余多少空间，够不够来装你。比如说现在我一个weight为3的背包，询问到了weight为1的物品，那我现在只有在刚好剩1个空间的情况下装你才刚刚好装满，即dp[2]，但之前这个dp[2]是有1 + 1 还是 单独一个2 构成的，这些我都不知道，也不关系，因为这是之前weight为2的背包考虑的问题，然后就是询问weight为2的物品，那这时当然是我只有在刚好剩2个空间的情况下装你才刚刚好装满，即dp[1]，dp[1] = 1显而易见，那这时装入背包的顺序，不久刚好是[1, 2]了吗。那如果多嘴追问一下说，那[2, 1]的顺序是什么时候被装入的呢，您忘了么，在询问weight为1的物品时就考虑到了呀，当时候就有可能是在[1, 1] 或 [2]的情况下装入这个weight为1的物品的，即当时就有了[1, 1, 1] 和 [2, 1]这两种装满背包的方法，那现在多一个[1, 2]对排列来说是正确的，无需去重。
int combinationSum4(vector<int>& nums, int target)
{
int size = nums.size();
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int j = 0; j <= target; ++j)
{
for (int i = 0; i < size; ++i)
{
if (j >= nums[i])
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}