题⽬
⼀只⻘蛙⼀次可以跳上1级台阶,也可以跳上2级。求该⻘蛙跳上⼀个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
示例1
输⼊:2
输出:2
解释:⻘蛙要跳上两级台阶有两种跳法,分别是:先跳⼀级,再跳⼀级或者直接跳两级。因此答案为2
示例2
输⼊:7
输出:21
示例3:
输⼊:0
输出:0
思路及解答
动态规划
这题和第7题 斐波那契数列 基本类似,只是换了一个题目表达方式。
青蛙跳到第n级台阶的跳法数 dp[i] 取决于两种最后一步的选择:
- 从第i-1级跳1级:跳法数为 dp[i-1]
- 从第i-2级跳2级:跳法数为 dp[i-2]
使用数组 dp,其中 dp[i] 表示跳到第 i 级台阶的跳法数
状态转移:dp[i] = dp[i-1] + dp[i-2],初始化 dp[1] = 1,dp[2] = 2
public int rectCover(int target){ if target <= 2{ return n } int[] dp = new int[n]; int dp[1] = 1; int dp[2] = 2; for (int i = 3; i <= target; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[target] }
- 时间复杂度 O(n)
- 空间复杂度 O(n)
动态规划(滚动数组优化)
观察状态转移方程,发现当前状态仅依赖前两个状态(dp[i-1] 和 dp[i-2]),因此只需保存这两个值,无需存储整个数组
public class Solution { public int rectCover(int target) { if (target <= 0) { return 0; } if (target < 3) { return target; } int num1 = 1; // 代表 dp[i-2] int num2 = 2; // 代表 dp[i-1] int result = 0; for (int i = 3; i <= target; i++) { result = num1 + num2; //更新前两项 num1 = num2; num2 = result; } return result; } }
- 时间复杂度 O(n)
- 空间复杂度 O(1)
如何思考空间优化方法?
- 观察状态依赖: 确认当前状态是否仅依赖有限的前几个状态(如斐波那契数列仅依赖前两项)
- 变量替换: 用固定数量的变量替代数组,滚动更新这些变量
- 边界处理: 初始化时需明确前几个状态的初始值(如 f(1) 和 f(2))