Triple Step: A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.
Hints: #152, #178, #217, #237, #262, #359.
解法1
如果第一次要走1个台阶，那么就只有一种走法(1)，剩余n - 1个台阶要走。
如果第一次要走2个台阶，那么有两种走法(1)、(2)，剩余n - 2个台阶要走。
如果第一次要走3个台阶，那么有4种走法(1,1,1)、(1,2)、(2,1)、(3)，剩余n - 4个台阶要走。
1
2
|
f(n) = f(n - 1) + f(2) * f(n - 2) + f(3) * f(n - 3)
= f(n - 1) + 2 * f(n - 2) + 4 * f(n - 3)
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public int tripleStep(int n) {
if (n == 1 || n == 2) {
return n;
}
if (n == 3) {
return 4;
}
int count = 0;
if (n - 1 > 0) {
count += tripleStep(n - 1);
}
if (n - 2 > 0) {
count += 2 * tripleStep(n - 2);
}
if (n - 3 > 0) {
count += 4 * tripleStep(n - 3);
}
return count;
}
|
时间复杂度：O(3n)
解法2
解法1存在重复计算，弄一个缓存：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public int tripleStep(int n, int[] cache) {
if (n == 1 || n == 2) {
return n;
}
if (n == 3) {
return 4;
}
if (cache[n] != 0) {
return cache[n];
}
int count = 0;
if (n - 1 > 0) {
count += tripleStep(n - 1);
}
if (n - 2 > 0) {
count += 2 * tripleStep(n - 2);
}
if (n - 3 > 0) {
count += 4 * tripleStep(n - 3);
}
cache[n] = count;
return count;
}
|
时间复杂度：O(n)
空间复杂度：O(n)
评论