Posted on 2022-12-12 17:59
Uriel 閱讀(47)
評論(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