一个小孩爬一个 n 层台阶的楼梯。他可以每次跳 1 步， 2 步 或者 3 步。实现一个方法来统计总共有多少种不同的方式爬到最顶层的台阶。
样例
n = 3
1 + 1 + 1 = 2 + 1 = 1 + 2 = 3 = 3
返回 4.
代码
public class Solution {
/**
* @param n an integer
* @return an integer
*/
public int climbStairs2(int n) {
// f[i]代表到达第i阶台阶的方式个数
int[] f = new int[n+1];
f[0] = 1;
for (int i = 0; i <= n; i++)
// f[i] = f[i - 1] + f[i - 2] + f[i - 3]
for (int j = 1; j <= 3; j++) {
if (i >= j) {
f[i] += f[i-j];
}
}
return f[n];
}
}
public class Solution {
/*
* @param n: An integer
* @return: An integer
*/
public int climbStairs2(int n) {
int last3 = 1;
int last2 = 1;
int last = 2;
if (n <= 1) {
return 1;
}
if (n == 2) {
return 2;
}
int now = 0;
for (int i = 3; i <= n; i++) {
// 这个赋值顺序要注意，last = now要放最后
// 如果写成last = now; last2 = last; last3 = last2;顺序则三个参量值都是now
now = last + last2 + last3;
last3 = last2;
last2 = last;
last = now;
}
return now;
}
}
