【动态规划】--爬楼梯

​
​

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…
…

题目：

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

代码：

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
        dp = [0 for _ in range(n + 1)]  # dp[i]表示爬到第i个台阶的时候方法数
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]  # 状态转移公式
        return dp[n]

1
2
3
4
5
6
7
8
9
10
11

学习日记

**
1，学习知识点

这题我们可以参照之前分析的青蛙跳台阶问题，其实原理是完全一样的
我们来分析一下：

当n等于1的时候，只需要跳一次即可，只有一种跳法，记f(1)=1
当n等于2的时候，可以先跳一级再跳一级，或者直接跳二级，共有2种跳法，记f(2)=2
当n等于3的时候，他可以从一级台阶上跳两步上来，也可以从二级台阶上跳一步上来，所以总共有f(3)=f(2)+f(1)；
同理当等于n的时候，总共有f(n)=f(n-1)+f(n-2)(这里n>2)种跳法。

​