Warning
本文最后更新于 July 31, 2022，文中内容可能已过时，请谨慎使用。
动态规划
讲解动态规划的资料很多，官方的定义是指把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。概念中的各阶段之间的关系，其实指的就是状态转移方程。很多人觉得DP难（下文统称动态规划为DP），根本原因是因为DP区别于一些固定形式的算法（比如DFS、二分法、KMP），没有实际的步骤规定第一步第二步来做什么，所以准确的说，DP其实是一种解决问题的思想。
动态规划的关键在于状态的定义，比如 opt[n] 、dp[n]、fib[n] 等。另外就是状态转移方程：opt[n] = best_of(opt[n-1], opt[n-2], …)
No.70 爬楼梯
为了从1开始计算到n，每层楼梯有多少种爬法，还需要一次循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| func climbStairs(n int) int {
if n == 1 {
return 1
}
dp := make([]int, n+1)
dp[1] = 1 // 一层楼梯1种爬法
dp[2] = 2 // 两层楼梯2种爬法，一次爬2层，爬2个一层
for i := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
|
No.746 使用最小花费爬楼梯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func min(a,b int) int {
if a > b {
return b
} else {
return a
}
}
func minCostClimbingStairs(cost []int) int {
n := len(cost)
dp := make([]int, n+1)
dp[0] = 0
dp[1] = 0
for i := 2; i <= n; i++ {
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
}
return dp[n]
}
|
No.121 买卖股票的最佳时机
比如：[7, 1, 5, 3, 6, 4] , 最大获利是 5
[1,2,3,4,5] 最大获利是4
[7,6,3,2] 最大获利就是0
这个题的思路就从历史最低点买入，存入历史最低值。用之后的数减去最低值。
其实并不是一道动态规划的做法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func maxProfit(prices []int) int {
var max int
var minProfile int = 1000000
n := len(prices)
for i := 0 ; i < n; i++ {
if minProfile > prices[i] {
minProfile = prices[i]
}
if prices[i] - minProfile > max {
max = prices[i] - minProfile
}
}
return max
}
|
No.152 乘积最大子数组
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
| func max3(a,b,c int) int {
if a >= b && a >= c {
return a
}
if b >= c && b >= a {
return b
}
return c
}
func min3(a,b,c int) int {
if a <= b && a <= c {
return a
}
if b <= a && b <= c {
return b
}
return c
}
func maxProduct(nums []int) int {
if len(nums) == 0 {
return 0
}
dp1 := make(map[int]int)
dp2 := make(map[int]int)
dp1[0] = nums[0] // 存最大
dp2[0] = nums[0] // 存最小，一个负数 * 一个负数可能最大
max := dp1[0]
for i := 1; i < len(nums); i ++ {
dp1[i] = max3(nums[i], nums[i]*dp1[i-1], nums[i]*dp2[i-1])
dp2[i] = min3(nums[i], nums[i]*dp1[i-1], nums[i]*dp2[i-1])
if dp1[i] > max {
max = dp1[i]
}
}
return max
}
|
No.300 最长递增子序列
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
| func lengthOfLIS(nums []int) int {
if len(nums) == 0 {
return 0
}
maxV := 1
// 使用切片来实现 dp 数组
dp := make([]int, len(nums))
// 初始化 dp 数组，每个元素初始值为 1
for i := range dp {
dp[i] = 1
}
for i := 1; i < len(nums); i++ {
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
dp[i] = max(dp[i], dp[j]+1)
}
}
maxV = max(maxV, dp[i])
}
return maxV
}
|
No.392 判断子序列
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
| func isSubsequence(s string, t string) bool {
m, n := len(s), len(t)
// 创建二维数组 dp 用于存储状态
dp := make([][]bool, m+1)
for i := range dp {
dp[i] = make([]bool, n+1)
}
// 初始化：空字符串是任何字符串的子序列
for j := 0; j <= n; j++ {
dp[0][j] = true
}
// 动态规划填充 dp 数组
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if s[i-1] == t[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = dp[i][j-1]
}
}
}
return dp[m][n]
}
|
第二种方法，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func isSubsequence(s string, t string) bool {
index := 0
var flag bool
for i := 0 ; i < len(s); i++ {
flag = false
for k := index ; k < len(t) ; k++ { // 循环长字符串
if t[k] == s[i] {
index = k+1 // 记录已找到的部分，下次从这继续开始找
flag = true
if i+1 == len(s) { // 短字符串已经遍历到头了
return flag
}
break
}
}
if flag == false {
return flag
}
}
return false
}
|
No.509 斐波那契数
1
2
3
4
5
6
7
8
9
10
11
12
13
| func fib(n int) int {
if n == 0 {
return 0
}
var dp []int
dp = make([]int, n+1)
dp[0] = 0
dp[1] = 1
for i := 2;i <= n; i ++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
|
No53. 最大子序和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func maxSubArray(nums []int) int {
var dp []int
dp = make([]int, len(nums))
dp[0] = nums[0]
for i := 1; i < len(nums) ; i++ {
dp[i] = max(dp[i-1]+ nums[i], nums[i])
}
max := -10000000000
for _, v := range dp {
if v > max {
max = v
}
}
return max
}
|
No.198 打家劫舍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func rob(nums []int) int {
if len(nums) == 0 {
return 0
}
if len(nums) == 1 {
return nums[0]
}
dp := make([]int, len(nums))
m := 0
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i := 2; i < len(nums) ; i++ {
dp[i] = max(dp[i-2]+nums[i], dp[i-1]) // 上上家和本家还是上家
}
for _, v := range dp {
if m < v {
m = v
}
}
return m
}
|
No.118 杨辉三角
1
2
3
4
5
6
7
8
9
10
11
12
| func generate(numRows int) [][]int {
ans := make([][]int, numRows)
for i := 0; i < numRows; i ++ {
ans[i] = make([]int, i+1)
ans[i][0] = 1
ans[i][i] = 1
for j := 1; j < i; j++ {
ans[i][j] = ans[i-1][j] + ans[i-1][j-1]
}
}
return ans
}
|
No.120 三角形最小路径和
2
3 4
6 5 7
4 1 8 3
随便选一个节点，如何判断到达此节点的最小路径呢。比如最后一行的数字 1 , dp[3][1] , 其最小值是从 dp[2][0] 和 dp[2][1] 里选一个。以此类推，一个标准的 dp。
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
| func minimumTotal(triangle [][]int) int {
if len(triangle) < 1 {
return 0
}
if len(triangle) == 1 {
return triangle[0][0]
}
dp := make([][]int, len(triangle))
for i, arr := range triangle {
dp[i] = make([]int, len(arr))
}
dp[0][0] = triangle[0][0]
for i := 1 ; i < len(triangle); i ++ {
for j := 0 ; j < len(triangle[i]); j ++ {
if j == 0 { // j 是三角左边只能选择侧边
dp[i][j] = triangle[i][j] + dp[i-1][0]
}else if j == len(triangle[i])-1 { // j 是三角右边，只能选侧边
dp[i][j] = triangle[i][j] + dp[i-1][j-1]
}else { // 三角中间，随便选
dp[i][j] = min(triangle[i][j] + dp[i-1][j], triangle[i][j] + dp[i-1][j-1])
}
}
}
min := 1000000000000
lastLevel := dp[len(triangle)-1]
for _, v := range lastLevel {
if v < min {
min = v
}
}
return min
}
|
No.64 最小路径和
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
| func minPathSum(grid [][]int) int {
if len(grid) == 0 {
return 0
}
if len(grid) == 1 && len(grid[0]) == 1 { // 1 x 1 正方形
return grid[0][0]
}
var length, width int
dp := make([][]int, len(grid))
for i, _ := range grid {
dp[i] = make([]int, len(grid[0]))
}
width = len(grid)
length = len(grid[0])
//fmt.Println(length, width)
for i := 0; i < len(grid); i ++ {
for j := 0; j < len(grid[i]); j ++ {
if i == 0 && j == 0 {
dp[0][0] = grid[0][0]
} else if i == 0 { // 第一层，没有上层
dp[i][j] = grid[i][j] + dp[i][j-1]
} else if j == 0 { // 第一列，没有左边
dp[i][j] = grid[i][j] + dp[i-1][j]
} else { // 左边或者上边
dp[i][j] = min(grid[i][j] + dp[i-1][j], grid[i][j] + dp[i][j-1])
}
}
}
return dp[width-1][length-1]
}
|
No.322 零钱兑换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
// 初始化dp[0]
dp[0] = 0
for i := 1; i <= amount; i++ { // 总金额逐渐递增
dp[i] = math.MaxInt32
for j := 0; j < len(coins); j ++ {
if i >= coins[j] { // dp[i]会被更新len(coins)次、找到差最少的
dp[i] = min(dp[i], dp[i-coins[j]] + 1)
}
}
}
// 没找到刚好 == 总额的
if dp[amount] == math.MaxInt32 {
return -1
}
return dp[amount]
}
|