跳台阶问题

UTOOLS1563427476706.png

动态规划的实际应用

1. 跳台阶

1.1 分析

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。

跳台阶问题属于动态规划类型的题目。举个样例,当只有1阶台阶时,只有一种方法到达楼顶,即走一步就到达;当有2阶台阶时,有两种方法到达楼顶,即:

1
2
1. 1阶 + 1
2. 2

我们可以想象在爬3阶台阶时,最后一步只有两种走法:即走1阶或者2阶。当最后一步为1阶时,下面还有2阶楼梯;当最后一步为2阶时,下面还有1阶楼梯。因此我们可得:

1
2
3
4
5
6
7
8
9
10
当最后一步为1阶时:
1 12阶台阶的走法1
/
1
\
22阶台阶的走法2


当最后一步为2阶时:
2 - 11阶台阶的走法)

所以我们总结出:3阶台阶的走法 = 2阶台阶的走法 + 1阶台阶的走法 = 1 + 2 = 3。通过这个结论,我们来模拟一下4阶台阶的所有走法:

1
2
3
4
5
6
7
8
9
10
11
12
13
当最后一步为1阶时
1 1 13阶台阶走法1
/
1 —— 1 1 23阶台阶走法2
\
2 1 (3阶台阶走法3)

当最后一步为2阶时
1 12阶台阶的走法1
/
2
\
22阶台阶的走法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)

1.2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
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.3 拓展

如果每次你可以爬 1 或 2 或 3 个台阶呢?实际上是相同,最后一步也只有1阶、2阶、3阶的走法,可得状态转移方程为:

1
f(n) = f(n - 1) + f(n - 2) + f(n - 3)

边界条件为:

1
2
3
当 n = 1时,有1种走法,即1
当 n = 2时,有2种走法,即1-12
当 n = 3时,有4种走法,即1-1-11-1-22-1-13

2. 变态跳台阶

2.1 分析

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶……也可以爬n阶台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。

变态跳台阶的关键点在于一步允许跳 [1, n] 阶台阶,因此最后一步就可以跳 [1, n] 阶,所以可以得出关系式:

1
2
3
4
5
6
7
8
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)

2.2 代码

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
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),那么直接返回结果即可:

1
2
3
public int JumpFloorII(int target) {
return 1 << --target; // 位运算代替指数运算
}
Pushy wechat
欢迎订阅我的微信公众号