Day45 | 70. 爬楼梯 （进阶）, 322. 零钱兑换, 279.完全平方数
爬楼梯（进阶）
LeetCode题目：https://leetcode.cn/problems/climbing-stairs/
爬楼梯问题现在可以抽象成一个完全背包的排列问题。因为每次指定上一个台阶或者两个台阶，所以可以看成有两个分别重量和价值均为1,2的物品可以反复取用。台阶即为背包的容量。
因此，由以上推理，问题可以化为：当可以取到x的台阶容量时，有多少种方法组成。即此时dp的容量上限为x，dp[i]意为容量为x时最多有多少种组合方法。所以递推公式为dp[j] += dp[j - nums[i]];
最终两次循环第一轮循环背包容量，第二轮循环物品价值，代码如下：
class Solution {
public:int climbStairs(int n) {if(n==1) return 1;vector<int> dp(n+1,0);dp[1] = 1;dp[2] = 2;for (int i = 3;i <= n;i++) {for(int j = 1; j <= 2; j++) {dp[i] += dp[i - j];}}return dp[n];}
};
零钱兑换
LeetCode题目：https://leetcode.cn/problems/coin-change/
该问题与零钱兑换ii不同的是只求所需要的硬币数量，而不在乎硬币的种类组合等。因此完全背包的循环顺序先背包还是先物品容量均可。如果要组合则只能先物品容量循环。
因此，还是求最小装满数量，所以dp数组代表容量为i的时候装满所需要的最小数量。递推公式可得为dp[j] = min(dp[j-coins[i]] + 1,dp[j])。由于涉及到最小值计算，则dp里面数值应该初始化为INT_MAX。并在每次循环是判定，如果dp[j-coins[i]]==INT_MAX，则意味着之前的dp[j-coins[i]]就没有办法装满，因此后续也无法装满。当循环结束，如果dp[amount] == INT_MAX则说明无法装满，所以置为-1.
最终两次循环，代码如下：
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) continue;dp[j] = min(dp[j - coins[i]] + 1, dp[j]); }}if(dp[amount] == INT_MAX) dp[amount] = -1;return dp[amount];}
};
完全平方数
LeetCode题目：https://leetcode.cn/problems/perfect-squares/
该问题与零钱兑换类似，只不过物品价值信息没有提前给出，而是需要循环时候自己判定完全平方数的存在。同时因为是求装满的最小数量，不需要纠结循环顺序，因此为了方便，可以将物品价值作为外循环，进行平方数判定。同时平方数的上限可以由n的边界得到。
因此，还是求最小装满数量，所以dp数组代表容量为i的时候装满所需要的最小数量。递推公式可得为dp[j] = min(dp[j-i] + 1,dp[j])。由于涉及到最小值计算，则dp里面数值应该初始化为INT_MAX。并在每次循环是判定，如果dp[j-i]==INT_MAX，则意味着之前的dp[j-i]就没有办法装满，因此后续也无法装满。但因为1也是完全平方数，所以基本不会有影响。
最终两次循环，代码如下：
class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i < 1e4 + 1; i++) {int a = (int)sqrt(i);if (a * a == i) {for (int j = i; j <= n; j++) {if(dp[j - i] == INT_MAX) continue;dp[j] = min(dp[j - i] + 1, dp[j]);}}}return dp[n];}
};
