如果代码出问题了,就把dp table 打印出来,看看究竟是不是和自己推导的一样。
此时大家应该发现了,这不就是斐波那契数列么!
唯一的区别是,没有讨论dp[0]应该是什么,因为dp[0]在本题没有意义!
-------------------
代码:
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2, sum = 0;
for (int i = 3; i <= n; i++) {
sum = a + b;
a = b;
b = sum;
}
return sum;
}
}
常规方法
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}