【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析

这篇具有很好参考价值的文章主要介绍了【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划

动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重复计算。

动态规划与数学归纳法思想上十分相似。

数学归纳法:

  1. 基础步骤(base case):首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况,可以直接验证命题是否成立。

  2. 归纳步骤(inductive step):假设命题在某个情况下成立,然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。

通过反复迭代归纳步骤,我们可以推导出命题在所有情况下成立的结论。

动态规划:

  1. 状态表示:

  2. 状态转移方程:

  3. 初始化:

  4. 填表顺序:

  5. 返回值:

数学归纳法的基础步骤相当于动态规划中初始化步骤。

数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。

动态规划的思想和数学归纳法思想类似。

在动态规划中,首先得到状态在最小的基础情况下的值,然后通过状态转移方程,得到下一个状态的值,反复迭代,最终得到我们期望的状态下的值。

接下来我们通过三道例题,深入理解动态规划思想,以及实现动态规划的具体步骤。

518. 零钱兑换 II - 力扣(LeetCode)

题目解析

【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析,动态规划,动态规划,算法,c++

状态表示

这个问题本质上是,

  1. 从一些数中挑选一些数出来,然后再满足某些限定条件下,解决一些问题。而背包问题就是用来解决组合问题。

  2. 每一个物品都是无限多个,因此属于完全背包问题。

完全背包实际上是一个模版,我们根据完全背包的状态表示,去定义我们希望得到的状态表示。

完全背包的状态表示是,

定义dp[i][j]表示从前i个物品中挑选,总体积不超过j,所有选法中,所能达到的最大价值。

定义dp[i][j]表示从前i个物品中挑选,总体积恰好为j,所有选法中,所能达到的最大价值。

因此我们可以定义dp[i][j]表示从前i个硬币中挑选,总和正好为j,一共有多少种选法。

状态转移方程

【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析,动态规划,动态规划,算法,c++

根据最后一个位置的具体情况进行分类讨论。

  1. 如果选择0个第i个硬币, 此时相当于在前i-1个硬币中挑选,总和正好为j,一共有多少种选法。此时dp[i][j]=dp[i-1][j]。

  2. 如果选择1个第i个硬币, 此时相当于,在前i-1个硬币中挑选,总和正好为j-coins[i],一共有多少种选法,在这些选法中,把1个第i个硬币放进去,此时的选法就等于在前i个硬币中挑选,总和正好为j,而这时候有多少种选法呢?有dp[i-1][j-coins[i]]种选法,此时dp[i][j]=dp[i-1][j-coins[i]]。

  3. 如果选择2个第i个硬币, 此时相当于,在前i-1个硬币中挑选,总和正好为j-2*coins[i],一共有多少种选法,在这些选法中,把2个第i个硬币放进去,此时的选法就等于在前i个硬币中挑选,总和正好为j,而这时候有多少种选法呢?有dp[i-1][j-2*coins[i]]种选法,此时dp[i][j]=dp[i-1][j-2*coins[i]]。

  4. ............

  5. 一直到全部选择第i个硬币为止。

综上所述,dp[i][j]=dp[i-1][j]+dp[i-1][j-coins[i]]+dp[i-1][j-2*coins[i]]+.........

我们发现一个很有趣的东西,等式的右边,横坐标不变,纵坐标依次减少coins[i],因此我们可以尝试推导dp[i][j-coins[i]]。

dp[i][j-coins[i]]=dp[i-1][j-coins[i]]+dp[i-1][j-2*coins[i]]+........,而

dp[i][j]=dp[i-1][j]+dp[i-1][j-coins[i]]+dp[i-1][j-2*coins[i]]+.........,

因此我们可以把dp[i][j]写成这样,dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]];

这样我们就将O(n)减低成O(1)。

而上述coins[i]表示的并不是表示第i个硬币,因为coins[0]表示第一个硬币,所以第i个硬币应该是coins[i-1]表示第i个硬币,所以,状态转移方程应该为,dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];

综上所述,状态转移方程为,

 
            dp[i][j] = dp[i - 1][j];
            if (j - coins[i - 1] >= 0)
                dp[i][j] += dp[i][j - coins[i - 1]];

初始化

【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析,动态规划,动态规划,算法,c++

根据状态转移方程,我们知道在推导(i,j)位置状态的时候,需要用到(i-1,j)(i,j-coins[i-1])位置的状态。而使用(i,j-coins[i-1])状态时,j-coins[i-1]>=0,此时一定不会越界,所以我们只需要考虑(i-1,j)位置状态即可。

在蓝色部分,即第一行,会发生越界的情况,此时初始化这些位置的状态时,没有前驱状态值,所以我们需要初始化这些位置的状态。

第一行i==0,表示不选择硬币,硬币总和为j,一共的选法,此时(0,0)位置为1,即不选一种方法,而其他位置都为0,没有选法可以达到。其他位置是不存在,而不存在正常来说要用特殊的标志表示,但是在这道题中,用0表示不存在也不会有影响。所以不存在也用0表示。

综上所述,初始化为,

 
   dp[0][0] = 1;

填表顺序

根据状态转移方程,我们知道在推导(i,j)位置状态的时候,需要用到(i-1,j)(i,j-coins[i-1])位置的状态。

  1. 固定i改变j, i的变化需要从小到大,因为可能要用到(i,j-coins[i-1])的状态,所以j的变化也需要从小到大。

  2. 固定j改变i, j的变化需要从小到大,因为可能要用到(i-1,j)位置的状态,所以i的变化也需要从小到大。

返回值

状态表示为,定义dp[i][j]表示从前i个硬币中挑选,总和正好为j,一共有多少种选法。

结合题目意思,我们要返回,从前n个硬币中挑选,总和正好为m,一共有多少种选法。

故返回dp[n][m],(m为amount)

代码实现

 
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        int m = amount;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - coins[i - 1] >= 0)
                    dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }

        return dp[n][m];
    }
};

279. 完全平方数 - 力扣(LeetCode)

【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析,动态规划,动态规划,算法,c++

题目解析

【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析,动态规划,动态规划,算法,c++

状态表示

这个问题本质上是,

  1. 从一些数中挑选一些数出来,然后再满足某些限定条件下,解决一些问题。而背包问题就是用来解决组合问题。

  2. 每一个物品都是无限多个,因此属于完全背包问题。

完全背包实际上是一个模版,我们根据完全背包的状态表示,去定义我们希望得到的状态表示。

完全背包的状态表示是,

定义dp[i][j]表示从前i个物品中挑选,总体积不超过j,所有选法中,所能达到的最大价值。

定义dp[i][j]表示从前i个物品中挑选,总体积恰好为j,所有选法中,所能达到的最大价值。

因此我们可以定义dp[i][j]表示从前i个数的完全平方数中挑选,总和正好为j,完全平方数的最少数量。

状态转移方程

【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析,动态规划,动态规划,算法,c++

根据最后一个位置的具体情况进行分类讨论。

  1. 如果选择0个第i个数的完全平方数, 此时相当于在前i-1个数的完全平方数中挑选,总和正好为j,这种情况下完全平方数的最少数量,此时dp[i][j]=dp[i-1][j]。i

  2. 如果选择1个第i个数的完全平方数, 此时相当于在前i-1个数的完全平方数中挑选,总和正好为j-i^2,完全平方数的最少数量,此时再加上1个第i个数的完全平方数,相当于在前i个数的完全平方数中挑选,总和正好为j,这种情况下完全平方数的最少数量,即dp[i][j]=dp[i-1][j-i^2]+1。

  3. 如果选择2个第i个数的完全平方数, 此时相当于在前i-1个数的完全平方数中挑选,总和正好为j-2*i^2,完全平方数的最少数量,此时再加上2个第i个数的完全平方数,相当于在前i个数的完全平方数中挑选,总和正好为j,这种情况下完全平方数的最少数量,即dp[i][j]=dp[i-1][j-2*i^2]+2。

  4. ..........

  5. 一直到全部选择第i个数的完全平方数。

综上所述,dp[i][j]=min(dp[i-1][j],dp[i-1][j-i^2]+1,dp[i-1][j-2*i^2]+2,.........)

我们发现一个很有趣的东西,等式右边,横坐标不变,纵坐标依次减少i^2。因此我可以尝试推导dp[i][j-i^2]。

得到dp[i][j-i^2]=min(dp[i-1][j-i^2],dp[i-1][j-2*i^2]+1,dp[i-1][j-3*i^2]+2,........)

为了统一,dp[i][j-i^2]+1=min(dp[i-1][j-i^2]+1,dp[i-1][j-2*i^2]+2,dp[i-1][j-3*i^2]+3,........)

又dp[i][j]=min(dp[i-1][j],dp[i-1][j-i^2]+1,dp[i-1][j-2*i^2]+2,.........)

故可以将dp[i][j]写成这样,dp[i][j]=min(dp[i-1][j],dp[i][j-i^2]+1);

当dp[i-1][j]或者dp[i][j-i^2]不存在的时候,不能选到了他们,因此我们可以将不存在定义为INF=0x3f3f3f3f,因为是取两者小的一个,所以即使不存在也不会取到他们。

综上所述,状态转移方程为,

 
        dp[i][j] = dp[i - 1][j];
        if (j - i * i >= 0)
            dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);

初始化

【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析,动态规划,动态规划,算法,c++

根据状态转移方程,我们知道在推导(i,j)位置的状态时,需要用到(i-1,j)(i,j-i^2)的状态。

而用(i,j-i^2)的状态时,j-i^2一定不会越界,所以我们只需要考虑(i-1,j)的状态即可。

因此在推导第一行的状态时,会发生越界的情况,此时没有前驱状态值,所以我们需要初始化第一行的状态。

第一行,i==0,表示不选数,总和为j,平方数的个数,(0,0)位置状态应该初始化为0,其他位置状态为不存在,我们根据前面的分析,得出不存在应该初始化为0x3f3f3f3f。

填表顺序

根据状态转移方程,我们知道在推导(i,j)位置的状态时,需要用到(i-1,j)(i,j-i^2)的状态。

  1. 固定i,改变j, i的变化需要从小到大,因为要使用到(i,j-i^2)位置状态,所以j的变化也需要从小到大。

  2. 固定j,改变i, j的变化需要从小到大,因为要使用到(i-1,j)位置状态,所以i的变化也需要从小到大。

返回值

根据状态表示定义dp[i][j]表示从前i个数的完全平方数中挑选,总和正好为j,完全平方数的最少数量。

结合题目要求,我们需要返回,从前m个数的完全平方数中挑选,总和正好为n,完全平方数的最少数量。

(m的完全平方数应该小于等于n,而m+1的完全平方数>n)

返回dp[m][n];

代码实现

 
class Solution {
public:
    int numSquares(int n) {
        int m = 1;
        while (m * m <= n)
            m++;
        m--;
        int INF = 0x3f3f3f3f;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INF));
        dp[0][0] = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - i * i >= 0)
                    dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
            }
        }

        return dp[m][n];
    }
};

474. 一和零 - 力扣(LeetCode)

【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析,动态规划,动态规划,算法,c++

题目解析

【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析,动态规划,动态规划,算法,c++

状态表示

这个问题本质上是,

  1. 从一些数中挑选一些数出来,然后再满足某些限定条件下,解决一些问题。而背包问题就是用来解决组合问题。

  2. 每一个物品都是无限多个,因此属于完全背包问题。

完全背包实际上是一个模版,我们根据完全背包的状态表示,去定义我们希望得到的状态表示。

完全背包的状态表示是,

定义dp[i][j]表示从前i个物品中挑选,总体积不超过j,所有选法中,所能达到的最大价值。

定义dp[i][j]表示从前i个物品中挑选,总体积恰好为j,所有选法中,所能达到的最大价值。

因此我们可以定义dp[i][j][k]表示从前i个字符串中挑选,字符0的个数不超过j,字符1的个数不超过k,所有选法中,子集的最大个数。

状态转移方程

【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析,动态规划,动态规划,算法,c++

根据最后一个位置的具体情况进行分类讨论。

假设第i个字符串中,字符0的个数为a,字符1的个数为b。

  1. 不选第i个字符串, 相当于在前i-1个字符串里面挑选,使字符0的个数不超过j,字符1的个数不超过k,所有选法中,子集的最大个数。此时dp[i][j][k]=dp[i-1][j][k];

  2. 挑选第i个字符串, 那么接下来,我需要在前i-1个字符串里面挑选出一些字符串,使得字符0的个数不超过j-a,字符1的个数不超过k-b,然后在这些字符串中加入第i个字符串,此时相当于在前i个字符串里面挑选出一些字符串,使得字符0的个数不超过j,字符1的个数不超过k。此时dp[i][j][k]=dp[i-1][j-a][k-b]+1。

综上所述,状态转移方程为,

 
    dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-a][k-b]+1)

需要推导(i,j,k)位置的状态,需要用到(i-1,j,k)(i-1,j-a,k-b)位置的状态,使用前提就是不能越界,对于(i-1,j,k)可以初始化第一行处理,而对于(i-1,j-a,k-b)初始化不好处理,所以我们选择直接考虑其存在的情况,即if(j>=a&&k>=b)才使用。

因此状态转移方程可以写成,

 
        dp[i][j][k] = dp[i - 1][j][k];
        if (j >= a && k >= b)
            dp[i][j][k] =
                max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);

初始化

根据状态转移方程,我们知道想要推导(i,j,k)位置的状态时,需要用到(i-1,j,k)(i-1,j-a,k-b)位置的状态。而(i-1,j-a,k-b)位置的状态的使用,我们已经考虑过j-a,和k-b不越界的情况,所以我们只需要考虑i-1以及(i-1,j,k)位置状态不越界的情况。

因此我们需要初始化i==0的情况。

当i==0时,表示不选字符串,字符0个数不超过j,字符1的个数不超过k,所有情况中,字符串个数最大值。所以i==0时,所有位置状态应该为0。

填表顺序

根据状态转移方程,我们知道想要推导(i,j,k)位置的状态时,需要用到(i-1,j,k)(i-1,j-a,k-b)位置的状态。

  1. 固定i,改变j,改变k i的变化需要从小到大,j、k的变化可以从小到大也可以从大到小。因为i从小到大变化,就满足了在推导(i,j,k)位置状态时,(i-1,,)的状态已经得到。

  2. 固定j,改变i,改变k j的变化需要从小到大,因为需要用到(i-1,j,k)位置的状态,所以i的变化需要从小到大,k的变化可以从小到大也可以从大到小。

  3. 固定k,改变i,改变j k的变化需要从小到大,因为需要用到(i-1,j,k)位置的状态,所以i的变化需要从小到大,j的变化可以从小到大也可以从大到小。

这三种情况,后面的顺序都可以交换。

返回值

状态表示定义dp[i][j][k]表示从前i个字符串中挑选,字符0的个数不超过j,字符1的个数不超过k,所有选法中,子集的最大个数。

结合题目意思,我们需要从前len个字符串中挑选,字符0的个数不超过m,字符1的个数不超过n,所有选法中,子集的最大个数。所以我们需要返回dp[len][m][n],(len是strs中字符串的个数)

代码实现

 
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int len = strs.size();
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
        for (int i = 1; i <= len; i++) {

            int a = 0, b = 0;
            for (auto ch : strs[i - 1])
                if (ch == '0')
                    a++;
                else
                    b++;
            for (int j = m; j >= 0; j--)
                for (int k = n; k >= 0; k--) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= a && k >= b)
                        dp[i][j][k] =
                            max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);
                }
        }
        return dp[len][m][n];
    }
};

结尾

今天我们学习了动态规划的思想,动态规划思想和数学归纳法思想有一些类似,动态规划在模拟数学归纳法的过程,已知一个最简单的基础解,通过得到前项与后项的推导关系,由这个最简单的基础解,我们可以一步一步推导出我们希望得到的那个解,把我们得到的解依次存放在dp数组中,dp数组中对应的状态,就像是数列里面的每一项。最后感谢您阅读我的文章,对于动态规划系列,我会一直更新,如果您觉得内容有帮助,可以点赞加关注,以快速阅读最新文章。

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

谢谢您的支持,期待与您在下一篇文章中再次相遇!文章来源地址https://www.toymoban.com/news/detail-780401.html

到了这里,关于【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 算法打卡day39|动态规划篇07| Leetcode 70. 爬楼梯(进阶版)、322. 零钱兑换、279.完全平方数

    Leetcode 70. 爬楼梯(进阶版) 题目: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,

    2024年04月14日
    浏览(65)
  • 代码随想录第44天|动态规划:完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ

    代码随想录 (programmercarl.com) 动态规划之完全背包,装满背包有多少种方法?组合与排列有讲究!| LeetCode:518.零钱兑换II_哔哩哔哩_bilibili 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件 。 完全背包中的物品可以添加多次,所以要从小到大遍历: 518. 零钱兑换

    2024年04月25日
    浏览(44)
  • 【LeetCode题目详解】第九章 动态规划part06 完全背的讲解 518. 零钱兑换 II 377. 组合总和 Ⅳ (day44补)

    # 完全背包 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 每件物品都有无限个(也就是可以放入背包多次) ,求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件 。

    2024年02月09日
    浏览(38)
  • 动态规划part06 518. 零钱兑换 II 377. 组合总和 Ⅳ

     518 零钱兑换|| 377. 组合总和 Ⅳ  

    2024年01月20日
    浏览(50)
  • LeetCode518. 零钱兑换 II 以及 动态规划相关的排列组合问题

    一、题目 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 示例 1: 示

    2024年02月09日
    浏览(42)
  • leetcode 动态规划(爬楼梯、零钱兑换、完全平方数)

    卡码网:57. 爬楼梯(opens new window) 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,表

    2024年01月17日
    浏览(42)
  • 518. 零钱兑换 II -- 完全背包

    518. 零钱兑换 II 这道题其实就是一个 完全背包 问题,关于背包问题的相关文章见: 01背包问题 – 动态规划 完全背包问题

    2024年02月09日
    浏览(39)
  • day 45:爬楼梯进阶版;322. 零钱兑换;279. 完全平方数

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 一步一个台阶,两个台阶,三个台阶,…,直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢? dp[j]:爬到j层一共有多少种方法。 递推公式:dp[j] += dp[j - i]; dp[0] = 1; dp[i]:目标整数为i的背包所能凑的最少硬币

    2024年02月07日
    浏览(95)
  • 算法训练Day45:70. 爬楼梯 (进阶) 322. 零钱兑换 279.完全平方数

    Category Difficulty Likes Dislikes ContestSlug ProblemIndex Score algorithms Easy (54.04%) 2993 0 - - 0 Tags 记忆  |  数学  |  动态规划 Companies 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 示例 1: 示例 2: 提示: 1 = n = 45

    2024年02月01日
    浏览(45)
  • 算法训练第四十五天|70. 爬楼梯 (进阶)、322. 零钱兑换、279.完全平方数

    题目链接:70. 爬楼梯 (进阶) 参考:https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%89%88%E6%9C%AC.html 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数

    2023年04月26日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包