You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
dp = {}
dp[1] = 1
dp[2] = 2
for i in xrange(3, n+1):
dp[i] = dp[i-1]+dp[i-2]
return dp[n]
1 想要到达台阶i,有两种方式到达,第一种是从i-1台阶跨一步到达台阶i,第二种是从i-2台阶跨两步到达台阶i,所以到达台阶i的方式等于到达台阶i-1的方式+到达台阶i-2的方式。
2 而到达台阶i-1的方式又由i-3跨两步加上i-2跨一步得到,所以这个问题可以用动态规划来实现
3 找到初始的两个值dp[1]和dp[2],然后一步一步往上叠加,注意xrange中后面是n+1
4 最后返回dp[n]其实也包括dp[1]和dp[2],所以不需要单独再去写函数列出初始两个值
5 还有很关键的一点是dp在这定义的是一个dictionary,而不是一个数组,如果定义成一个数组也行,那我们每次需要append值到数组中去,这样下一次才好取出值来。不如定义成dictionary形式,每次取值也方便,时间复杂度很低
网友评论