爬楼梯

1. 满足条件才更新dp公式：if (j >= i * i && dp[j - i * i] != Integer.MAX_VALUE)

本题内外层顺序无关这里我写的是外层物品，内层背包（但是，这个题内外反过来也可以）

dp五步曲：

1. dp[i] 表示和为 i 的完全平方数的最小数量
2. 递推公式：dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
3. 初始化（同 322. 零钱兑换）

dp[0]=0;

其他的初始化为正无穷

1. 遍历顺序

本题内外层顺序无关，这里我写的是外层物品，内层背包

for (int i = 1; i < dp.length; i++) // 外层物品，内层背包

for (int j = i * i; j < dp.length; j++) // 内层背包

1. 打印dp

爬楼梯

这个题之前那样写的只能处理一次上一层、两层，但是如果一次能上1，2，...或 m 层呢？

如果是每次只能上小于m的奇数步的话，只用采取一个数组 steps 存放每次可以上楼梯的方案就行

那之前的就不太好写了，这时候其实这是个完全背包问题，因为：

1. 每次上的楼梯数（1阶，..m阶）看成物品，楼顶台阶数就是背包容量
2. 每个台阶数（相当于物品）可以重复使用，所以是完全背包
3. 然后，求得是能上到楼顶（相当于吧背包装满）的方案数量
4. 好了好了，背包装满的方案数量，就有如此相像。那不就是组合数或者排列数嘛！
5. 这个肯定是排列数，因为(1,2)和（2,1）是两种不同的方法

既然转化成求完全背包的排列数问题，那么就是套模板了

dp五步曲：

1. dp[i] 表示上到第 i 层的方案树
2. 完全背包（排列数固定递推公式）：dp[j] += dp[j - i];
3. 初始化：dp[0] = 1;

排列数固定初始化。又因为方案均为正数，其他的初始化为0就行了

1. 遍历顺序（排列数：必须是外层背包，内层物品）
2. 打印 dp