1. 跳台阶
分析
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
跳台阶问题属于动态规划类型的题目。举个样例，当只有1阶台阶时，只有一种方法到达楼顶，即走一步就到达；当有2阶台阶时，有两种方法到达楼顶，即：
1. 1阶 + 1阶
2. 2阶
我们可以想象在爬3阶台阶时，最后一步只有两种走法：即走1阶或者2阶。当最后一步为1阶时，下面还有2阶楼梯；当最后一步为2阶时，下面还有1阶楼梯。因此我们可得：
当最后一步为1阶时：
1 1 （2阶台阶的走法1）
/
1
\
2 （2阶台阶的走法2）
当最后一步为2阶时：
2 - 1 （1阶台阶的走法）
所以我们总结出：3阶台阶的走法 = 2阶台阶的走法 + 1阶台阶的走法 = 1 + 2 = 3。通过这个结论，我们来模拟一下4阶台阶的所有走法：
当最后一步为1阶时
1 1 1 （3阶台阶走法1）
/
1 —— 1 1 2 （3阶台阶走法2）
\
2 1 (3阶台阶走法3)
当最后一步为2阶时
1 1 （2阶台阶的走法1）
/
2
\
2 （2阶台阶的走法2）
因此4阶台阶的走法 = 3阶台阶的走法 + 2阶台阶的走法 = 3 + 2 = 5。因此得出公式：N阶台阶的走法 = N - 1 阶台阶走法 + N - 2 阶台阶的走法。有没有对这个等式似曾相识？对！实际上就是一个斐波那契数列的等式。因此我们得出动态规划的两个关键点：
- 边界条件：当
n = 1时，有1种走法；当n = 2时，有2种走法。 - 状态转移方程：
f(n) = f(n - 1) + f(n - 2)
代码
public int JumpFloor(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
int[] dp = new int[n];
// 初始化边界条件的值
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n - 1]; // 返回N阶台阶的走法
}
拓展
如果每次你可以爬 1 或 2 或 3 个台阶呢？实际上是相同，最后一步也只有1阶、2阶、3阶的走法，可得状态转移方程为：
f(n) = f(n - 1) + f(n - 2) + f(n - 3)
边界条件为：
当 n = 1时，有1种走法，即1
当 n = 2时，有2种走法，即1-1、2
当 n = 3时，有4种走法，即1-1-1、1-1-2、2-1-1、3
2. 变态跳台阶
分析
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶……也可以爬n阶台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
变态跳台阶的关键点在于一步允许跳 [1, n] 阶台阶，因此最后一步就可以跳 [1, n] 阶，所以可以得出关系式：
f(n) = 1（一步就到楼顶） + f(n - 1) + f(n - 2) + ... + f(1)
当 n = 1时, f(1) = 1 (2^0)
当 n = 2时，f(2) = 1 + f(1) = 2 (2^1)
当 n = 3时，f(3) = 1 + f(1) + f(2) = 4 (2^2)
当 n = 4时，f(4) = 1 + f(1) + f(2) + f(3) = 8 (2^3)
...
当 n = n时，f(n) = 1 + f(1) + f(2) + ... + f(n-1) = 2^(n-1)
代码
代码如下：
public int JumpFloorII(int n) {
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = 0; j < i; j++) {
sum += dp[j];
}
dp[i] = 1 + sum;
}
return dp[n - 1];
}
但是，既然掌握规律即f(n) = 2^(n-1)，那么直接返回结果即可：
public int JumpFloorII(int target) {
return 1 << --target; // 位运算代替指数运算
}