美文网首页动态规划
【Leetcode】Climbing Stairs

【Leetcode】Climbing Stairs

作者: 云端漫步_b5aa | 来源:发表于2018-10-23 12:27 被阅读4次

    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形式,每次取值也方便,时间复杂度很低

    相关文章

      网友评论

        本文标题:【Leetcode】Climbing Stairs

        本文链接:https://www.haomeiwen.com/subject/kknozftx.html