题目链接
思路
分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律
表示状态
假设走到了最后一层台阶,考虑一下我们要存储的信息:
- 走到这最后一层台阶的方法数
- 当前台阶数,用于判断是否走到了最后一层台阶
这时候很容易想到使用一维数组 dp[i]
来表示走到第 i 层台阶有多少种方法。
找状态转移方程
在第 i 层台阶处,我们可以看作两种情况:
- 从第 i-1 层台阶走了一步到第 i 层
- 从第 i-2 层台阶走了两步到第 i 层
这样可以得到状态转移方程
\[dp[i] = dp[i - 1] + dp[i - 2] \]边界处理
很容易知道 dp[1] = 1
且 dp[2] = 2
空间优化
因为 dp[i]
只与 dp[i - 1]
和 dp[i - 2]
有关,所以可以使用两个单变量 pre
和 pre2
分别表示 dp[i - 1]
和 dp[i - 2]
,同时不断滚动更新。
代码
dp
数组版
class Solution {
public int climbStairs(int n) {
// dp[i] = dp[i - 1] + dp[i - 2]
int[] dp = new int[n + 3];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
空间优化版
class Solution {
public int climbStairs(int n) {
// dp[i] = dp[i - 1] + dp[i - 2]
int pre = 1;
int pre2 = 2;
int result = pre + pre2;
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
for(int i = 3; i <= n; i++){
result = pre + pre2;
pre = pre2;
pre2 = result;
}
return result;
}
}
标签:pre,台阶,int,DP,70,LeetCode,dp,pre2
From: https://www.cnblogs.com/shixuanliu/p/17280294.html