jz10-Ⅱ.青蛙跳台阶问题

题目描述

题解

动态规划

这道题理解起来很容易, 运用动态规划的思想, 跳上第n阶台阶, 要么是从n-1阶跳上来的, 要么是从n-2阶跳上来的, 那么将两者相加即可.

.png)

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