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,意味着对于每层台阶,其上一次迈步都有若干种可能。文章来源:https://www.uudwc.com/A/3wjOO/
换零钱先遍历零钱,意味着对于每一种零钱,其上一个DP(金额)只能参与一次运算。文章来源地址https://www.uudwc.com/A/3wjOO/