LeetCode(剑指offer-Recursion)-面试题10- II. 青蛙跳台阶问题_综合

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

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

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

提示：

0 <= n <= 100

题源链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof

class Solution {
    
public:int numWays(int n) {
    if(n<2){
    return 1;}/*动态规划的关键就是：1.找到状态转移方程；2. 申请内存保存历史信息，这样就不用重复计算*/// 初始化数组// vector<int> dp(n+1, 0);int *dp = new int[n+1]; // +1是因为包括0// 初始条件dp[0] = 1;dp[1] = 1;for (int i=2; i<=n; i++){
    // n=2开始，满足斐波那契数列，// 动态规划状态转移方程满足：f(n) = f(n-1) + f(n-2)dp[i] = (dp[i-1] + dp[i-2]) % 1000000007; // 取余是为了防止越界}// 获取结果int result = dp[n];// 释放内存delete[]dp;return result;}
};

题解思路
在这里插入图片描述

class Solution {
    
public:int numWays(int n) {
    if(n<2){
    return 1;}/*动态规划的关键就是：1.找到状态转移方程；2. 申请内存保存历史信息，这样就不用重复计算*/int a = 1; // n-2int b = 1; // n-1int sum;for (int i=2; i<=n; i++){
    // n=2开始，满足斐波那契数列，// 动态规划状态转移方程满足：f(n) = f(n-1) + f(n-2)sum = (b + a) % 1000000007; // 取余是为了防止越界a = b;b = sum;}return sum;}
};

在这里插入图片描述