以下是今日份的总结
518 零钱兑换 II
377 组合总和 Ⅳ
70 爬楼梯
今天的题目难度不低，掌握技巧了就会很简单，尽量还是写一些简洁代码 ^ _ ^
零钱兑换 II
思路：
1.确定dp数组以及下标的含义
------ dp[j]：凑成总金额j的货币组合数为dp[j]
2.确定递推公式
------递推公式：dp[j] += dp[j - coins[i]];
3.dp数组如何初始化
------首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。
------其余非零下标均初始化为0
4.确定遍历顺序
------外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）
5.举例推导dp数组
值得注意的是
外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）//所以这种遍历顺序中dp[j]里计算的是组合数！
外层for循环遍历背包（金钱总额），内层for遍历物品（钱币）//此时dp[j]里算出来的就是排列数！
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];
}
组合总和 Ⅳ
思路：
1.确定dp数组以及下标的含义
------ dp[i]: 凑成目标正整数为i的排列个数为dp[i]
_
2.确定递推公式
------递推公式一般都是dp[i] += dp[i - nums[j]];
_
3.dp数组如何初始化
------在初始化的时候dp[0] 一定要初始化为1
------其余非零下标均初始化为0
_
4.确定遍历顺序
------外层for遍历背包，内层for循环遍历物品
_
5.举例推导dp数组
值得注意的是
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
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];
}
爬楼梯
思路：
1.确定dp数组以及下标的含义
------ dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。
2.确定递推公式
------递推公式为：dp[i] += dp[i - j]
3.dp数组如何初始化
------dp[0] 一定为1
------其余非零下标均初始化为0
4.确定遍历顺序
------排列数就是外层for遍历背包，内层for循环遍历物品。
5.举例推导dp数组
值得注意的是
同上
int climbStairs(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) { // 遍历背包
for (int j = 1; j <= 2; j++) { // 遍历物品
if (i - j >= 0) dp[i] += dp[i - j];
}
}
return dp[n];
}
写在最后
----OK，今日份的博客就写到这里，这一期的动态规划好难想，明天继续加油！！！
—还没看下期的题，但是我的栈还有一节没写；
–追不上时间进度了！！又欠了三天的（笑
-吃好，喝好，身体好；玩好，学好，心情好！！。
