本文共 1268 字，大约阅读时间需要 4 分钟。

此类求 多少种可能性 的题目一般都有 递推性质 ，即 f(n) 和 f(n-1)…f(1) 之间是有联系的。

• 设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。

1. 当为 1 级台阶： 剩 n-1 个台阶，此情况共有 f(n-1) 种跳法；
2. 当为 2 级台阶： 剩 n-2 个台阶，此情况共有 f(n-2) 种跳法。

• f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2) ，以上递推性质为斐波那契数列。本题可转化为 ，与 上一道题 等价，唯一的不同在于起始数字不同。
  • 青蛙跳台阶问题： f(0)=1, f(1)=1, f(2)=2；
  • 斐波那契数列问题： f(0)=0, f(1)=1, f(2)=1。
    

【动态规划的算法流程】

• 状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表 斐波那契数列第 i 个数字 。
• 转移方程： dp[i + 1] = dp[i] + dp[i - 1] ，即对应数列定义 f(n + 1) = f(n) + f(n - 1) ；
• 初始状态： dp[0] = 0, dp[1] = 1 ，即初始化前两个数字；
• 返回值： dp[n] ，即斐波那契数列的第 n 个数字。
  

class Solution:    def numWays(self, n: int) -> int:        a, b = 1, 1        for _ in range(n):            a, b = b, a + b        return a % 1000000007'''作者：jyd链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/solution/mian-shi-ti-10-ii-qing-wa-tiao-tai-jie-wen-ti-dong/'''

• 时间复杂度O(n)， 计算 f(n) 需循环 n 次，每轮循环内计算操作使用 O(1)；
• 空间复杂度O(1)， 几个标志变量使用常数大小的额外空间。

【扩展 - 】

我想说，这青蛙真变态，真能跳。

当n=1时，结果为1；

当n=2时，结果为2；

当n=3时，结果为4；

.

以此类推，我们使用数学归纳法不难发现，跳法f(n)=2^(n-1)。

class Solution:    def jumpFloorII(self, number):        if number <= 2:            return number        total = 1        for _ in range(1, number):            total *= 2        return total

转载地址：http://ofjii.baihongyu.com/