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

解题思路：动态规划

动态规划三大步：

  1. 定义状态转移方程
  2. 给定方程初始值
  3. 递推实现

首先，定义dp数组；dp[i] 表示 跳上第i级台阶共有多少种跳法

状态转移方程：

跳上第i级台阶的跳法有两种情况：

  1. 跳到第i - 1级台阶后再跳1级台阶
  2. 跳到第i - 2级台阶后再跳2级台阶

所以，可以确定状态转移方程为:

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

确定初始值:

  1. dp[0] = 1
  2. dp[1] = 1

代码

Java

  1. class Solution {
  2.     public int numWays(int n) {
  3.         // 动态规划
  4.         // dp[i] 表示 跳上第i级台阶共有多少种跳法
  5.         // 状态转移方程:
  6.         // dp[i] = dp[i - 1] + dp[i - 2]
  7.         // dp初始值:
  8.         // dp[0] = 1
  9.         // dp[1] = 1 跳上第1级台阶只有一种跳法
  10.         // dp[2] = 2 跳上第2级台阶有两种跳法：1. 每次跳1级；2. 直接跳2级
  11.         if(n == 0){
  12.             return 1;
  13.         }
  14.         if(n == 1){
  15.             return 1;
  16.         }
  17.         int[] dp = new int[n + 1];
  18.         dp[0] = 1;
  19.         dp[1] = 1;
  20.         for(int i = 2; i < n + 1; i++){
  21.             dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
  22.         }
  23.         return dp[n];
  24.     }
  25. }

复杂度分析

  • 时间复杂度：O(N)

通过动态规划的递推计算性质，可以知道时间复杂度为：O(N)

  • 空间复杂度：

需要开辟 dp 数组，占用的额外空间为：O(N)