LeetCode 刷题：跳台阶/爬楼梯问题

1 跳台阶11.1 问题描述1.2 解法1.2.1 动态规划1.2.2 递归

1 跳台阶1

原题链接：

剑指 Offer 10- II. 青蛙跳台阶问题70. 爬楼梯

1.1 问题描述

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

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

示例 1： 输入：n = 2 输出：2

示例 2： 输入：n = 7 输出：21

示例 3： 输入：n = 0 输出：1

提示：0 <= n <= 100

1.2 解法

1.2.1 动态规划

第 n 级楼梯的方法 = 爬到 n-1级楼梯再上一楼 + 爬到 n-2级楼梯再上一楼。因此是： $$f(n)=f(n-1)+f(n-2)$$ 可以直接用动态规划：

class Solution { public: int numWays(int n) { if (n == 0) return 1; if (n == 1) return 1; if (n == 2) return 2; vector<int> dp(101); dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i ++) { dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007; } return dp[n]; } };

1.2.2 递归

可以联想到斐波那契数列用递归，但缺点是比较慢（可以带memo）。

class Solution { public: int climbStairs(int n) { if (n < 1) return 0; // 备忘录全初始化为 0 vector<int> memo(n + 1, 0); // 初始化最简情况 return helper(memo, n); } int helper(vector<int>& memo, int n) { if (n == 1 || n == 2) return n; if (memo[n] != 0) return memo[n]; // 已经计算过 memo[n] = helper(memo, n - 1) + helper(memo, n - 2); return memo[n]; } };