剑指 Offer 10- II. 青蛙跳台阶问题

剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

思路

golang

这道题和上一题剑指 Offer 10- I. 斐波那契数列一样，采用递归会报超时
也是采用动态规划的思想。
动态规划三部曲：
1.初始状态：dp[0]=1，dp[1]=1，其中dp[i]表示i级楼梯共有多少种跳法
2.状态转移方程：dp[n] = dp[n-1]+dp[n-2]
3.返回值：dp[n]，n级台阶的跳法种数

func numWays(n int) int {
    if n==0||n==1{
        return 1
    }
    //初始状态
    dp := make([]int,n+1)
    dp[0],dp[1] = 1,1
    for i:=2;i<=n;i++{
        dp[i] = dp[i-1]+dp[i-2] //状态转移方程
        dp[i] %= 1000000007
    }
    return dp[n] //返回值
}

同样，也可以进行空间复杂度的优化

func numWays(n int) int {
	a, b, sum := 1, 1, 0
	for i := 0; i < n; i++ {
		sum = (a + b) % 1000000007
		a, b = b, sum
	}
	return a
}

js

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
    let a=1,b=1,sum=0;

    for(let i=0;i<n;i++){
        sum = (a+b)%1000000007;
        [a,b] = [b,sum]
    };
    return a;
};

剑指 Offer 10- II. 青蛙跳台阶问题

原文：https://www.cnblogs.com/zmk-c/p/14617882.html