爬楼梯-动态规划_爬楼梯算法 动态规划 共多少种

爬楼梯

思路

爬1楼：1种
爬2楼：2种
爬3楼：3种
爬4楼：5种
爬4楼可以看做爬2楼再往上走2步或爬3楼再往上走1步，因此爬4楼=爬3楼种数+爬2楼种数

• 动态规划
  1、 确定数组dp[i]及下标含义：dp[i]表示爬到第i层楼梯，有dp[i]种方法
  2、确定递推公式：dp[i]=dp[i-1]+dp[i-2]
  3、确定dp数组初始化：题目告知1<=n<=45,因此不考虑dp[0]的情况，dp[1]=1,dp[2]=2
  4、确定遍历顺序: 由递推公式可知，遍历顺序是从前往后
  5、举例推导递推数组：当n=5, 数组值为：1 2 3 5 8，数组下标：1 2 3 4 5
• 时间复杂度O(n)、空间复杂度O(n)

class Solution:
    def climbStairs(self, n: int) -> int:
        #动态规划，dp[i]=dp[i-1]+dp[i-2]
        if n<=1:
            return n
        dp=[0]*(n+1)
        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
12

• 时间复杂度O(n)、空间复杂度O(1)

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型
#
class Solution:
    def jumpFloor(self , number: int) -> int:
        # 动态规划dp[i]=dp[i-1]+dp[i-2]
        if number<=1:
            return number
        dp=[0]*(number+1)
        dp[1]=1
        dp[2]=2
        for i in range(3,number+1):
            tmp=dp[1]+dp[2]
            dp[1]=dp[2]
            dp[2]=tmp
        return dp[2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20