原来for循环并不能随意挪动嵌套关系

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（金额）只能参与一次运算。文章来源地址https://uudwc.com/A/3wjOO