之前已经做过这题了，实际上这题可以抽象成一个完全背包问题（只有两种物品，一个1一个2，但是可以无限取），接下来用动规五部曲重新分析一下。
- 确定dp数组及其含义
dp[j]表示爬楼梯为j时的爬法。
- 确定递推公式
跟之前组合问题总和一样，问的是爬法数量：
dp[j] = dp[j - value[i]]，其中value={1,2}
- dp数组初始化
dp[0] = 1；
- 确定遍历顺序
这是背包里求排列问题，即：1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！
所以需将target放在外循环，将nums放在内循环。
每一步可以走多次，这是完全背包，内循环需要从前向后遍历。
- 模拟打印dp数组
class Solution {public int climbStairs(int n) {if(n <= 2){return n;}int dp[] = new int[n + 1];//dp[n]表示到n阶的种数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];}
}
总结：排列先遍历背包，组合先遍历物品。
322. 零钱兑换
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
递推公式：dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
遍历顺序：不分排列组合，内外顺序无所谓，遍历背包从小到大。
最终代码：
class Solution {public int coinChange(int[] coins, int amount) {//dp[j]表示总金额为j时最少需要多少硬币int dp[] = new int[amount + 1];dp[0] = 0;for(int i = 1; i <= amount; i++){dp[i] = Integer.MAX_VALUE;}for(int i = 0; i < coins.length; i++){for(int j = coins[i]; j <= amount; j++){if(dp[j - coins[i]] != Integer.MAX_VALUE){dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}}return (dp[amount] == Integer.MAX_VALUE) ? -1:dp[amount];}
}
279. 完全平方数
跟上面那题一样，还是完全背包，不过换成用i的平方来填背包了：
class Solution {public int numSquares(int n) {int dp[] = new int[n + 1];//dp[i]表示和为i的完全平方数的最小数量。dp[0] = 0;for(int i = 1; i <= n; i++){dp[i] = Integer.MAX_VALUE;}for(int i = 0; i * i <= n; i++){for(int j = i * i; j <= n; j++){if(dp[j - i* i] != Integer.MAX_VALUE){dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}}return dp[n];}
}
- 递推公式：dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
- 遍历顺序：先物品，后背包，从小到大。
- 初始化：dp[0]=0,其余为最大值。
