剑指 Offer 10- II. 青蛙跳台阶问题（简单）思路：代码：分解：

83 阅读 0 评论 55 点赞

我是靠谱客的博主威武指甲油，这篇文章主要介绍剑指 Offer 10- II. 青蛙跳台阶问题（简单）思路：代码：分解：，现在分享给大家，希望可以做个参考。

思路：

此题与剑指offer 10-I一样，都有三种方法：

i）递归

ii）非递归：

1）动态规划dp数组

2）动态规划优化的常量存值

具体代码可看博文：（https://blog.csdn.net/di_ko/article/details/115818352）

代码：

方法二：

class Solution {
    public int numWays(int n) {
		int[] dp=new int[n];
		
		if(n<2) return n;
		dp[0]=0;
		dp[1]=1;
		
		for(int i=2;i<=n;i++){
			dp[i]=dp[i-1]+dp[i-2];
			dp[i]=dp[i]%1000000007;
		}
		return dp[n];
    }
}

方法三：

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