探寻剑指Offer第8题:台阶跳跃之策新探
题目
有一只青蛙,一次能跳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 target;
}
int[] dp = new int[target + 1];
dp[1] = 1;
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)
)
相关文章
暂无评论...