青蛙跳台阶问题

Posted on In Views: Waline: Views: Symbols count in article: 215 Reading time ≈ 1 mins.

题解方法

  • 动态规划

动态规划

  • 每一级台阶只能从前一级或前两级台阶上跳跃而来

$$
dp[i] = dp[i - 1] + dp[i - 2]
$$

核心代码

动态规划

1
2
3
4
5
6
7
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;

for (int i = 3; i <= n; i++) {
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
}

题目来源

剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（LeetCode）