2023年9月26日我参加了一次小米技术面试二面，面试官人很不错，感觉也很照顾我，在手撕代码这里给了两个EASY，然而我只做出来了一个，另一个当时脑子宕机了，没做出来。经过仔细复盘，发现原来这里面真的有坑，而且我把自己引导到坑里面去了。
题目很简单，是力扣70题，爬楼梯。
题目描述：假设你正在爬楼梯。需要 `n` 阶你才能到达楼顶。每次你可以爬 `1` 或 `2` 个台阶。你有多少种不同的方法可以爬到楼顶呢？
这道题，本身是非常简单的，如果放到笔试里，估计很快就能做出来，但是面试的时候确实是第一时间没想明白，后续就开始发蒙了。
我当时的思路是类比换零钱这道题，但是换零钱和爬楼梯是有区别的，在此之前我根本没想到这一层关系。
换零钱的题目描述如下：
题目描述：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。
先看一下两道题的解法。(为了方便对比，对爬楼梯的函数参数进行了修改)
//这是爬楼梯(力扣70)
int climbStairs(int n，vector<int> &step)
{vector<int> dp(n + 1);dp[0] = 1;for (int i = 1; i <= n; i++){for (auto j : step){if (j > i){continue;}dp[i] += dp[i - j];}}return dp[n];
}
//这是换零钱(力扣518)
int change(int amount, vector<int> &coins)
{vector<int> dp(amount + 1);dp[0] = 1;for (auto j : coins){for (int i = j; i <= amount; i++){dp[i] += dp[i - j];}}return dp[amount];
}
很明显，除了循环嵌套顺序不一样，其他的毫无区别。
那么这两种循环嵌套有什么区别呢？
简单来说就是排列和组合的区别，爬楼梯是排列，换零钱是组合。
爬楼梯，假设有1个3阶台阶，那我可以先走2步再走1步，或者先走1步再走2步。
换零钱，假设有1张3块钱，可以换成1张1块钱和1张2块钱，但这仅代表一种组合。
这也是上述两道题目循环嵌套的逻辑。
爬楼梯先遍历DP，意味着对于每层台阶，其上一次迈步都有若干种可能。
换零钱先遍历零钱，意味着对于每一种零钱，其上一个DP（金额）只能参与一次运算。
