Climbing Stairs 上台阶方式总数计算
博客专区 > codetask 的博客 > 博客详情
Climbing Stairs 上台阶方式总数计算
codetask 发表于1年前
Climbing Stairs 上台阶方式总数计算
  • 发表于 1年前
  • 阅读 0
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

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):

        if n < 4:

            return n

        pfirst = 1

        psecond = 1

        all_ways = 3

        for i in range(4,n+1):

            pfirst,psecond = pfirst+psecond,pfirst

            all_ways += pfirst

        return all_ways

 

 

 

 

过程:

#上面可以看出

6 = 4+5

5 = 3+4

4 = 2+3

3 = 1+2

 

#则直接使用递归 R(n-1) + R(n-2) 就可以得出结果

#OK, 但超出了时间限制!!!

 

#--------------------------------------------------

#重新来一次

#--------------------------------------------------

 

1 (1)

2 (2)

3 (3)

4 (5)

5 (8)

6 (13)

 

#上面可以看出:

1  +0   1

2  +1   2

3  +1   3

4  +2   5

5  +3   8

6  +5   13

7  +8   21

 

#从第3个台阶往后走就是相加最后2个走过的台阶数

#so.

###############################################

#设置2个虚拟指针 pfirst   psecond

#从4开始计算  最后的台阶数3就是开始的基准数字

1  +0   1

2  +1   2       < psecond   =1

3  +1   3       < pfirst    =1

4  +2   5

5  +3   8

6  +5   13

7  +8   21

 

1+1=2

#计算完时虚拟指针是这样的状态:

1  +0   1

2  +1   2

3  +1   3       < psecond   =1

4  +2   5       < pfirst    =2

5  +3   8

6  +5   13

7  +8   21

 

#计算4的当前台阶数就是

      (2)

3 + pfirst = 5

 

###############################################

#

#下面计算5

#上面计算出了4的台阶数是5  所以当前基准数字为5

1  +0   1

2  +1   2

3  +1   3       < psecond   =1

4  +2   5       < pfirst    =2

5  +3   8

6  +5   13

7  +8   21

 

1+2=3

#计算完时虚拟指针是这样的状态:

1  +0   1

2  +1   2

3  +1   3

4  +2   5       < psecond   =2

5  +3   8       < pfirst    =3

6  +5   13

7  +8   21

 

#计算5的当前台阶数就是

    (3)

5 + pfirst = 8

 

############################### OK!

  • 点赞
  • 收藏
  • 分享
粉丝 6
博文 102
码字总数 25743
作品 1