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

Love The Way You Lie 2022-10-16 09:51 120阅读 0赞

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

*  题目难度：简单
 *  方法一：动态规划

> 链接：[https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/][https_leetcode-cn.com_problems_qing-wa-tiao-tai-jie-wen-ti-lcof]  
> 来源：力扣（LeetCode）图解算法数据结构

# 题目难度：简单 #

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

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

示例 1：

输入：n = 2
    输出：2

示例 2：

输入：n = 7
    输出：21

示例 3：

输入：n = 0
    输出：1

限制：

0 <= n <= 100

模板

class Solution {
        
        public int numWays(int n) {
        
    
        }
    }

# 方法一：动态规划 #

**解题思路：**

设跳上  n n n 级台阶有  f ( n ) f(n) f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： **跳上  1 1 1 级或  2 2 2 级台阶**。

*  **当为  1 1 1 级台阶**： 剩  n − 1 n−1 n−1 个台阶，此情况共有  f ( n − 1 ) f(n−1) f(n−1) 种跳法；
 *  **当为  2 2 2 级台阶**： 剩  n − 2 n−2 n−2 个台阶，此情况共有  f ( n − 2 ) f(n−2) f(n−2) 种跳法。

即  f ( n ) f(n) f(n) 为以上两种情况之和，即  f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n−1)+f(n−2) f(n)=f(n−1)\+f(n−2) ，以上递推性质为斐波那契数列。

因此，本题可转化为 求斐波那契数列第  n n n 项的值 ，与 `剑指Offer 10- I. 斐波那契数列` 等价，唯一的不同的是初始化状态不一样

*  青蛙跳台阶问题：  f ( 0 ) = 1 , f ( 1 ) = 1 , f ( 2 ) = 2 f(0)=1 , f(1)=1 , f(2)=2 f(0)=1,f(1)=1,f(2)=2 ；
 *  斐波那契数列问题： f ( 0 ) = 0 , f ( 1 ) = 1 , f ( 2 ) = 1 f(0)=0 , f(1)=1 , f(2)=1 f(0)=0,f(1)=1,f(2)=1 。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70_pic_center]  
斐波那契数列的定义是  f ( n + 1 ) = f ( n ) + f ( n − 1 ) f(n + 1) = f(n) + f(n - 1) f(n\+1)=f(n)\+f(n−1) ，生成第  n n n 项的做法有以下几种：

1、 递归法：

*  **原理**： 把  f ( n ) f(n) f(n) 问题的计算拆分成  f ( n − 1 ) f(n−1) f(n−1) 和  f ( n − 2 ) f(n−2) f(n−2) 两个子问题的计算，并递归，以  f ( 0 ) f(0) f(0) 和  f ( 1 ) f(1) f(1) 为终止条件。
 *  **缺点**： 大量重复的递归计算，例如  f ( n ) f(n) f(n) 和  f ( n − 1 ) f(n−1) f(n−1) 两者向下递归都需要计算  f ( n − 2 ) f(n−2) f(n−2) 的值。

2、记忆化搜索：

*  **原理**：在递归法的基础上，新建一个长度为  n n n 的数组，用于在递归时存储  f ( 0 ) f(0) f(0) 至  f ( n ) f(n) f(n) 的数字值，重复遇到某数字时则直接从数组取用，避免了重复的递归计算。
 *  **缺点**：记忆化存储的数组需要使用  O ( N ) O(N) O(N) 的额外空间。

3、动态规划：

*  **原理**：以斐波那契数列性质  f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n-1) + f(n - 2) f(n)=f(n−1)\+f(n−2) 为转移方程。
 *  从计算效率、空间复杂度上看，动态规划是本题的最佳解法。

动态规划解析：三部曲

*  **状态定义**： 设  d p dp dp 为一维数组，其中  d p \[ i \] dp\[i\] dp\[i\] 的值代表跳到第  i i i 层共有多少种方法。
 *  **转移方程**：  d p \[ i \] = d p \[ i − 1 \] + d p \[ i − 2 \] dp\[i\]=dp\[i-1\]+dp\[i−2\] dp\[i\]=dp\[i−1\]\+dp\[i−2\] ，即对应数列定义  f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n−2) f(n)=f(n−1)\+f(n−2) ；
 *  **初始状态**：  d p \[ 1 \] = 1 , d p \[ 2 \] = 2 dp\[1\] = 1, dp\[2\]=2 dp\[1\]=1,dp\[2\]=2 ，即初始化前两个数字；
 *  **返回值**：  d p \[ n \] dp\[n\] dp\[n\] ，即跳到第  n n n 阶有多少种方法

**空间复杂度降低：**

> 若新建长度为  n n n 的  d p dp dp 列表，则空间复杂度为  O ( N ) O(N) O(N) 。

*  由于  d p dp dp 列表第  i i i 项只与第  i − 1 i−1 i−1 和第  i − 2 i−2 i−2 项有关，因此只需要初始化三个整形变量 `sum`, `a`, `b` ，利用辅助变量 `sum` 使 `a`, `b` 两数字交替进行即可
 *  因为节省了  d p dp dp 列表空间，因此空间复杂度降至  O ( 1 ) O(1) O(1)

**循环求余法：**

> 大数越界： 随着  n n n 增大,  f ( n ) f(n) f(n) 会超过 `Int32` 甚至 `Int64` 的取值范围，导致最终的返回值错误。

*  **求余运算规则**： 设正整数  x , y , p x, y, p x,y,p ，求余符号为  ⊙ \\odot ⊙ ，则有  ( x + y ) ⊙ p = ( x ⊙ p + y ⊙ p ) ⊙ p (x + y) \\odot p = (x \\odot p + y \\odot p) \\odot p (x\+y)⊙p=(x⊙p\+y⊙p)⊙p。
 *  **解析**： 根据以上规则，可推出  f ( n ) ⊙ p = \[ f ( n − 1 ) ⊙ p + f ( n − 2 ) ⊙ p \] ⊙ p f(n) \\odot p = \[f(n-1) \\odot p + f(n-2) \\odot p\] \\odot p f(n)⊙p=\[f(n−1)⊙p\+f(n−2)⊙p\]⊙p ，从而可以在循环过程中每次计算  s u m = a + b ⊙ 1000000007 sum = a + b \\odot 1000000007 sum=a\+b⊙1000000007 ，此操作与最终返回前取余等价。

class Solution {
        
        public int numWays(int n) {
        
            if (n == 0 || n == 1) return 1;
    
            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]) % 1_000_000_007;
            }
            return dp[n];
        }
    }

优化：

class Solution {
        
        public int numWays(int n) {
        
            if (n == 0 || n == 1) {
        
                return 1;
            }
            // pre表示第一阶台阶的共有多少走法
            // cur表示第二阶台阶的共有多少走法
            int pre = 1, cur = 2;
            for (int i = 3; i <= n; i++) {
        
                int sum = (pre + cur) % 1_000_000_007;
                pre = cur;
                cur = sum;
            }
            return cur;
        }
    }

[https_leetcode-cn.com_problems_qing-wa-tiao-tai-jie-wen-ti-lcof]: https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/a1fbc579d33d434ab634099a1fb0d459.png