动态规划--爬楼梯

心已赠人 2022-05-23 07:47 214阅读 0赞

1、题目：

You are climbing a stair case. It takes *n* steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given *n* will be a positive integer.

Example 1:

Input: 2
    Output: 2
    Explanation: There are two ways to climb to the top.
    1. 1 step + 1 step
    2. 2 steps

Example 2:

Input: 3
    Output: 3
    Explanation: There are three ways to climb to the top.
    1. 1 step + 1 step + 1 step
    2. 1 step + 2 steps
    3. 2 steps + 1 step

2、解答： 假设第n步，你可以由n-1步，走1步到达第n步，n-2，走2步到达第n步。

3、代码：

C++代码

class Solution {
    public:
        int climbStairs(int n) {
            vector<int> f(n+1,0);
            f[0] = 1;
            f[1] = 1;
            for(int i=2;i<=n;i++)
                f[i] = f[i-1] +f[i-2];
                
            return f[n];
        }
    };

python代码

class Solution:
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n < 1:
                return 0
            
            f = [1 for i in range(n+1)]
            
            for i in range(2,len(f)):
                f[i] = f[i-1] + f[i-2]
            
            return f[n]

发表评论取消回复

表情：

评论列表（有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_动态规划_简单_70.爬楼梯

目录 1.题目 2.思路 3.代码实现（Java） 1.题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台

绝地灬酷狼/ 2023年10月06日 19:17/ 0 赞/ 7 阅读

相关动态规划之爬楼梯

[70. 爬楼梯][70.] 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

迷南。/ 2023年09月30日 21:14/ 0 赞/ 11 阅读

相关利用动态规划求解爬楼梯问题

题目描述：假设你正在爬楼梯，需要n阶才能到达楼顶。每次可以爬1或2阶，你有多少种不同的方法可以爬到楼顶呢？其中n是一个正整数。思路和算法：利用动态规划，用f

约定不等于承诺〃/ 2022年12月28日 05:30/ 0 赞/ 171 阅读

相关算法题目——爬楼梯(动态规划)

题目链接：[70.爬楼梯][70.] 类似题目：[1646.获取生成数组中最大值][1646.] ![在这里插入图片描述][watermark_type_ZHJvaWRz

╰+哭是因爲堅強的太久メ/ 2022年09月14日 11:14/ 0 赞/ 212 阅读

相关 LeetCode（初级算法）动态规划篇---爬楼梯

题目假设你正在爬楼梯。需要 n 步你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例

末蓝、/ 2022年05月25日 13:44/ 0 赞/ 202 阅读

相关动态规划--爬楼梯

1、题目： You are climbing a stair case. It takes n steps to reach to the top. Each time y

心已赠人/ 2022年05月23日 07:47/ 0 赞/ 215 阅读

相关动态规划--最小代价爬楼梯

1、题目： On a staircase, the `i`\-th step has some non-negative cost `cost[i]` assigned (0

Myth丶恋晨/ 2022年05月23日 07:46/ 0 赞/ 220 阅读

相关 [算法提高] 动态规划爬楼梯

\[问题背景\] 来源：LeetCode(力扣) 编号：[70. 爬楼梯][70.] 内容：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或

喜欢ヅ旅行/ 2022年03月06日 04:03/ 0 赞/ 242 阅读

相关动态规划爬楼梯问题Java代码实现

题目描述：有 n 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法思路：第n阶楼梯，可以由n-1和n-2一步到达。用dp(n)代表方法数，dp(n)=dp(n-1)+

小鱼儿/ 2022年01月31日 04:59/ 0 赞/ 253 阅读

相关 [动态规划] 70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。超出时

约定不等于承诺〃/ 2021年12月09日 00:19/ 0 赞/ 269 阅读