剑指Offer[10-2]-青蛙跳台阶问题

题目

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

python代码

class Solution(object):
    def __init__(self):
        self._mod = 10**9+7
    def numWays(self, n):
        if n==0:
            return 1
        if n==1:
            return 1
        if n==2:
            return 2
        f1 = 1
        f2 = 2
        temp = 0
        for i in range(n-2):
            temp = f1 + f2
            f1 = f2
            f2 = temp
        return temp%self._mod

这道题属于动态规划的范畴,我们只需找好初始状态、子结构及传递关系。

初始条件就是:
– 当只有一个台阶时,只有一种跳法
– 当只有两个个台阶时,有两种跳法

子结构:
– 我们要求n个台阶需要多少种跳法,那么第n阶一定是从n-1阶或者n-2阶跳上去的,所以f(n)只与f(n-1)、f(n-2)有关

传递关系:
– f(n) = f(n-1) + f(n-2)

结语

当我们遇到最优化问题时,均可尝试动态规划方法来做,而动态规划解决问题的关键是寻找子结构,传递关系和初始条件一般很容易确定。

发表评论

电子邮件地址不会被公开。