但行好事,莫问前程

挖了太多坑,一点点填回来

算法题:爬楼梯算法

实战, 算法, 编程, 递归

有这样一个题目:应该是大学时代的经典算法题了——小孩上楼梯。

有个小孩正在上楼梯,楼梯有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
}

打完收工。