有这样一个题目：应该是大学时代的经典算法题了——小孩上楼梯。
有个小孩正在上楼梯，楼梯有s阶台阶，小孩一次可以上1阶或2阶。实现一个算法，计算小孩有多少种上楼梯的方式。输入n，返回一个整数。
稍微想了一下，这个题目可以用递归来解决。根据题目的规则，最后一步只有两种走法：要么走1阶，要么走2阶。所以可以得出这么一个递归公式：f(s) = f(s-1) + f(s-2)。好像就是一个斐波那契数列公式？
这个问题的边界值就是在只有1阶的情况下，只有1种方式(1)；在只有2阶的情况下，有两种方式(1,1)、(2)。
编写程序如下：
(stair.go) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| package main
import "fmt"
func main() {
// 默认走10阶
fmt.Println(GoStair(10))
}
func GoStair(s int) int {
if s < 1 {
return 0
}
if s < 3 {
return s
}
return GoStair(s-1) + GoStair(s-2)
}
|
使用正常的递归，在递归层数过多的情况下，可能会有stack overflow的风险，所以可以改写为用循环处理的方式：
(stair_with_loop.go) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| package main
import "fmt"
func main() {
// 默认走10阶
fmt.Println(GoStairWithLoop(10))
}
func GoStairWithLoop(s int) int {
// f(1) = 1
// f(2) = 2
// result是f(1)的值 tmp是f(2)-f(1)的值
result, tmp := 1, 1
for ; s != 0; {
tmp = result + tmp
result = tmp - result
s--
}
return result
}
|
将循环中使用到的变量提取出来作为函数的参数使用，就成了尾递归。在方法最后被调用时，线程栈里面的临时变量与参数此时已经没任何用了，可以被GC回收，所以理论上就是同上面的循环方法是一致的，无论有多深，都不会发生内存异常。
(stair_with_tail.go) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| package main
import "fmt"
func main() {
// 默认走10阶
fmt.Println(GoStairWithTail(10, 1, 1))
}
func GoStairWithTail(s int, result int, tmp int) int {
if s < 1 {
return result
}
return GoStairWithTail(s-1, tmp, result+tmp)
}
|
这种情况下，该算法的时间复杂度是O(n)。
下面扩展一下思路：
这小屁孩的老师作业留少了，闲着没事爬楼梯，楼梯有s阶台阶(steps)，小孩一次可以上m阶（maxStep）。计算小孩有多少种上楼梯的方式。输入s,m，返回一个整数。
一样分析可以得到公式：f(s) = f(s-1) + f(s-2) + ... + f(s-m)。
参照上例思路，我们可以在递归里分为两大部分，一部分是steps > maxStep时，参照f(s,m) = f(s-1) + f(s-2) + f(s-3) + … + f(s-m)进行累加。
我们现在看steps <= maxStep时，怎么给出类似上例里f(2)，f(3)的返回值。其实，上例中的f(3)，就是台阶一共3级，最大可以跨2步的值，即f(2) 就是f(2,2)，f(3)就是f(3,2)。分析一下就得出下面的图解：
根据以上图解，分析如下：
1
2
3
4
| steps > maxStep 时，f(s,m) = f(s-1) + f(s-2) + f(s-3) + ··· + f(s-m);
steps <= maxStep时，f(s,s) = f(s,s-1) +1;
steps = 1时，return 1;
steps = 0时，return 0;
|
编码如下：
(stair_with_s_m.go) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| package main
import "fmt"
func main() {
// 默认走10阶，每次最多2阶
fmt.Println(GoStairWithSM(10, 2))
}
func GoStairWithSM(s int, m int) int {
if s == 0 {
return 0
}
if s == 1 {
return 1
}
result := 0
if s > m {
for i := 1; i <= m; i++ {
result += GoStairWithSM(s-i, m)
}
} else {
result = GoStairWithSM(s, s-1) + 1
}
return result
}
|
打完收工。