Posted on 2022-12-12 17:59
Uriel 阅读(38)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
闲来无事重切Leet Code
爬楼梯，每次可以上一级或者两级台阶，问走到第n级一共多少走法，简单dp，状态转移方程：
dp[i] = dp[i -
1] + dp[i -
2]
写法一，简单写法
1 #70
2 #Runtime: 14 ms
3 #Memory: 13.5 MB
4 #2022.12.12
5
6 class Solution(object):
7 def climbStairs(self, n):
8 """
9 :type n: int
10 :rtype: int
11 """
12 dp = [1] * (n + 1)
13 for i in range(2, n + 1):
14 dp[i] = dp[i - 1] + dp[i - 2]
15 return dp[n]
写法二，试图不要开dp数组，用两个pre变量记录上一步和上两步的结果，但没省什么内存
1 #70
2 #Runtime: 12 ms
3 #Memory: 13.4 MB
4 #2021.01.21
5
6 class Solution(object):
7 def climbStairs(self, n):
8 """
9 :type n: int
10 :rtype: int
11 """
12 for i in range(1, n + 1):
13 if i == 1:
14 dp = 1
15 pre_1 =1
16 elif i == 2:
17 dp = 2
18 pre_2 = 1
19 pre_1 = 2
20 else:
21 dp = pre_1 + pre_2
22 pre_2 = pre_1
23 pre_1 = dp
24 return dp