原来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://www.uudwc.com/A/3wjOO/

原文地址:https://blog.csdn.net/xrn1997/article/details/133377768

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

上一篇 2023年10月05日 22:42
C# 自定义控件库之Lable组合控件
下一篇 2023年10月06日 00:12