Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
爬楼梯,每次可以上一级或者两级台阶,问走到第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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理