0%

《数据结构与算法》动态规划

题目

有一座高度是10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。

比如,每次走1级台阶,一共走10步,这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。

分析

想一想,如果楼梯只有一级台阶,总共有几种走法,很明显,只有一种

如果楼梯只有两级台阶,总共有几种走法,也很明显,只有两种

如果楼梯有3层台阶呢?

要么从第1个台阶走到第3个台阶,要么从第2个台阶走到第3个台阶,所以走向第3个台阶的走法种数应该等于走向第1个台阶的走法种数加上走向第2个台阶的走法种数

以此类推,走向第4个台阶的走法种数应该等于走向第2个台阶的走法种数加上走向第3个台阶的走法种数

走向第n个台阶的走法种数应该等于走向第n-2个台阶的走法种数加上走向第n-1个台阶的走法种数

也就是 f(n) = f(n-1) + f(n-2),f(1) = 1,f(2) = 2

上面的思想就是动态规划思想

f(n) = f(n-1) + f(n-2)是状态转移方程

f(1) = 1,f(2) = 2是边界

下面就可以写代码求解,最直观的解法就是递归

解答

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

import (
"fmt"
)

func test(n int) int {
if n < 1 {
return 0
}
if n == 2 {
return 2
}
if n == 1 {
return 1
}
return test(n-1) + test(n-2)
}

func main() {
fmt.Println(test(10))
}

非常直观简单,但是看看时间复杂度,是O(2^n)

仔细想想会发现很多被重复计算,假设n=10,第一次递归会计算f(8)和f(9),第二次递归会计算f(7)和f(8),f(8)被重复计算

那么肯定有更好的算法

既然被重复计算,那么就可以利用缓存避免重复计算,下面看更好的算法

备忘录算法

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package main

import (
"fmt"
"time"
)

func test1(map_ map[int]int, n int) int {
if n < 1 {
return 0
}
if n == 2 {
return 2
}
if n == 1 {
return 1
}
if result, ok := map_[n]; ok {
return result
}
n1 := test1(map_, n-1)
n2 := test1(map_, n-2)
map_[n] = n1 + n2
return n1 + n2
}

func test(n int) int {
if n < 1 {
return 0
}
if n == 2 {
return 2
}
if n == 1 {
return 1
}
return test(n-1) + test(n-2)
}

func main() {
n := 30

t0 := time.Now()
fmt.Println(test1(make(map[int]int, n), n))
fmt.Println(time.Now().Sub(t0)) // 38.144µs

t1 := time.Now()
fmt.Println(test(n))
fmt.Println(time.Now().Sub(t1)) // 3.82213ms
}

缓存结果之后可以看出时间上的差异。那么这个时候时间复杂度是多少呢

因为有缓存,所以不会向前面一样有重复计算,所以只会计算n次,所以复杂度是O(n)

而空间复杂度则是O(n),有没有空间复杂度更低的办法,其实是有的,看下面

迭代

其实我们可以使用迭代来替代递归的做法,相对来说递归是比较晦涩的

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package main

import (
"fmt"
"time"
)

func test1(map_ map[int]int, n int) int {
if n < 1 {
return 0
}
if n == 2 {
return 2
}
if n == 1 {
return 1
}
if result, ok := map_[n]; ok {
return result
}
n1 := test1(map_, n-1)
n2 := test1(map_, n-2)
map_[n] = n1 + n2
return n1 + n2
}

func test(n int) int {
if n < 1 {
return 0
}
if n == 2 {
return 2
}
if n == 1 {
return 1
}
return test(n-1) + test(n-2)
}

func test2(n int) int {
result := 0
cache1 := 1
cache2 := 2
for i := 3; i <= n; i++ {
result = cache1 + cache2
cache1 = cache2
cache2 = result
}
return result
}

func main() {
n := 30

t0 := time.Now()
fmt.Println(test1(make(map[int]int, n), n))
fmt.Println(time.Now().Sub(t0)) // 38.144µs

t1 := time.Now()
fmt.Println(test(n))
fmt.Println(time.Now().Sub(t1)) // 3.82213ms

t2 := time.Now()
fmt.Println(test2(n))
fmt.Println(time.Now().Sub(t2)) // 12.516µs
}

可以看到迭代时间复杂度O(n),空间复杂度O(1),是最完美的算法




微信关注我,及时接收最新技术文章