动态规划(Dynamic Programing)，通过解决存储子问题结果，迭代h解决整个问题

斐波纳切数列(fibbonacci)

1

0,1,1,2,3,5,8,13,21,34

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

//n ≥ 3
func fibbonacciDynamic(n int) []int {
	table := make([]int, n+1)
	table[0] = 0
	table[1] = 1
	for i := 2; i <= n; i++ {
    // 动态规划，子问题环环相扣构成母问题
		table[i] = table[i-1] + table[i-2] 
	}

	return table
}

func fibbonacci(n int) int {
	if n < 2 {
		return n
	}
	return fibbonacci(n-1) + fibbonacci(n-2)
}

解码

一条包含字母 A-Z 的消息通过以下方式进行了编码：

1
2
3
4

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

1
2
3

"12" #2
"01" #0
"226" #3

提示：状态转移方程需要分类讨论»

通配符匹配

1
2

s = "aab"
p = "a*ab"

子序列匹配失败，则母序列一定失败；

显然p为空时，s 只有为空才能匹配成功。s为空时，p为空或全为*时匹配。

如：s取子序列为空 "" p取子序列"","a", "a*" "a*a" "a*ab" 

1
2
3
4

0 1 1 1 1   # 纵坐标为s的子序列 横坐标为p的子序列
1 
1
1