08.算法——动态规划

算法专题：动态规划 (Dynamic Programming)

1. 引言

在计算机科学和数学中，动态规划（Dynamic Programming，简称 DP）是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它通常用于优化问题，即在给定约束条件下，找到最大或最小的某个值。

动态规划的核心思想是，如果一个问题可以被分解成相互重叠的子问题，并且这些子问题的最优解可以组合成原问题的最优解（即具有最优子结构），那么就可以使用动态规划。通过存储和重用子问题的解，DP 算法避免了重复计算，从而显著提高了效率，通常将指数级的暴力搜索优化到多项式时间。

2. 动态规划的两个核心特性

一个问题能够用动态规划解决，通常需要满足以下两个关键性质：

2.1 最优子结构 (Optimal Substructure)

  • 定义：一个问题的最优解包含其子问题的最优解。
  • 理解：这意味着如果你找到了解决一个大问题的最佳方法，那么这个方法所涉及的每个小步骤（子问题）也必须是以最佳方式解决的。
  • 例子：如果最短路径问题中从 A 到 B 的最短路径经过 C，那么从 A 到 C 的路径以及从 C 到 B 的路径也必须是各自的最短路径。

2.2 重叠子问题 (Overlapping Subproblems)

  • 定义：在解决问题的过程中，会多次遇到相同的子问题。
  • 理解：如果子问题是独立的（比如快速排序），那么用分治法就足够了；但如果子问题会被多次计算，那么就可以通过存储子问题的解来避免重复计算，这就是动态规划的优势所在。
  • 例子：计算斐波那契数列 F(n)，F(n) = F(n-1) + F(n-2)。计算 F(5) 需要 F(4) 和 F(3)，而 F(4) 又需要 F(3) 和 F(2)，F(3) 被计算了多次。

3. 动态规划的两种实现方式

动态规划通常有两种主要的实现方式：

3.1 记忆化搜索 (Memoization / Top-down DP)

  • 思想：自顶向下，递归地解决问题。在计算子问题时，将结果存储起来（通常在数组或哈希表中）。下次再遇到相同的子问题时，直接从存储中读取，而不是重新计算。
  • 优点：
    • 更接近直觉的递归思路，容易编写。
    • 只计算真正需要的子问题。
  • 缺点：
    • 递归调用可能导致栈溢出。
    • 有函数调用的额外开销。

3.2 列表法 / 递推 (Tabulation / Bottom-up DP)

  • 思想：自底向上，迭代地解决问题。从最小的子问题开始，逐步计算并填充一个表格（通常是数组），直到计算出原问题的解。
  • 优点：
    • 没有递归开销，通常更高效。
    • 避免栈溢出。
    • 更容易进行空间优化。
  • 缺点：
    • 需要确定正确的计算顺序。
    • 可能需要计算所有子问题，即使某些子问题对最终解没有贡献。

4. 解决动态规划问题的通用步骤

  1. **定义状态 (State)**：确定 dp 数组的含义，即 dp[i] 或 dp[i][j] 代表什么。
  2. **初始化 (Initialization)**：确定 dp 数组的初始值（边界条件）。
  3. **确定状态转移方程 (Recurrence Relation)**：找出如何从已知的子问题的解推导出当前问题的解。
  4. **确定遍历顺序 (Iteration Order)**：保证在计算 dp[i] 或 dp[i][j] 时，其依赖的子问题已经被计算过。
  5. **打印遍历与确定返回值 (Result)**：如果存在疑惑可打印输出，以便于确定最终答案在 dp 数组中的位置。

5. 动态规划与贪心算法/回溯算法的区别

  • 与贪心算法：
    • 贪心：每一步都做出局部最优选择，不考虑全局影响，且不回溯。要求问题具有“贪心选择性质”。通常更简单高效，但适用范围窄。
    • DP：考虑所有子问题的最优解，通过组合子问题解来得到全局最优，可能会在计算过程中探索多个路径。要求问题具有“最优子结构”和“重叠子问题”。适用范围更广。
  • 与回溯算法：
    • 回溯：一种暴力搜索，通过尝试所有可能的路径来找到解，当遇到死路或不满足条件时回溯。通常会进行剪枝来优化。
    • DP：在回溯的基础上，通过存储和重用重叠子问题的解来避免重复计算，从而将指数级复杂度降低到多项式级。可以看作是带有记忆化的回溯，或者说是“去掉了重复计算的回溯”。

6. Go 语言实现示例

示例1：斐波那契数列 (Fibonacci Number)

问题：计算第 n 个斐波那契数。F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)。

1. 记忆化搜索 (Top-down)

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
package main

import "fmt"

var memo map[int]int // 用于存储已计算的斐波那契数

func fibMemo(n int) int {
	// 初始化 memo 맵
	if memo == nil {
		memo = make(map[int]int)
	}

	// 1. 基本情况 (Base Cases)
	if n <= 1 {
		return n
	}

	// 2. 检查是否已计算 (重叠子问题)
	if val, ok := memo[n]; ok {
		return val
	}

	// 3. 状态转移方程 (递推关系)
	// fibMemo(n) = fibMemo(n-1) + fibMemo(n-2)
	res := fibMemo(n-1) + fibMemo(n-2)

	// 4. 存储结果
	memo[n] = res
	return res
}

// 清除 memo 供多次测试
func resetMemo() {
	memo = nil
}

func main() {
	fmt.Println("--- 斐波那契数列 (记忆化搜索) ---")
	resetMemo() // 清除之前的记忆
	fmt.Printf("F(10) = %d\n", fibMemo(10)) // 55
	resetMemo()
	fmt.Printf("F(20) = %d\n", fibMemo(20)) // 6765
}

2. 列表法 (Bottom-up)

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
package main

import "fmt"

func fibTabulation(n int) int {
	// 1. 基本情况 (Base Cases)
	if n <= 1 {
		return n
	}

	// 2. 定义 DP 状态: dp[i] 表示第 i 个斐波那契数
	dp := make([]int, n+1) // dp 数组大小为 n+1，索引 0 到 n

	// 初始化基本情况
	dp[0] = 0
	dp[1] = 1

	// 3. 确定计算顺序并推导状态转移方程
	// 从小到大计算，确保 dp[i-1] 和 dp[i-2] 已计算
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}

	return dp[n]
}

func main() {
	fmt.Println("\n--- 斐波那契数列 (列表法) ---")
	fmt.Printf("F(10) = %d\n", fibTabulation(10)) // 55
	fmt.Printf("F(20) = %d\n", fibTabulation(20)) // 6765
	fmt.Printf("F(0) = %d\n", fibTabulation(0))   // 0
	fmt.Printf("F(1) = %d\n", fibTabulation(1))   // 1
}

示例2：凑零钱问题 (Coin Change)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 完全背包问题思路
func coinChange(coins []int, amount int) int {
	n := len(coins)
	dp := make([]int, amount+1)
	dp[0] = 0
	for i := 1; i < len(dp); i++ {
		dp[i] = math.MaxInt64
	}
	for i := 0; i < n; i++ {
		for j := coins[i]; j <= amount; j++ {
			if dp[j-coins[i]] != math.MaxInt64 {
				dp[j] = min(dp[j], dp[j-coins[i]]+1)
			}

		}
	}
	// 没找到能装满背包的, 就返回-1
	if dp[amount] == math.MaxInt64 {
		return -1
	}
	return dp[amount]
}

示例3：最长公共子序列 (Longest Common Subsequence, LCS)

问题：给定两个字符串 text1 和 text2，找出这两个字符串的最长公共子序列的长度。子序列是指一个字符串通过删除一些（或不删除）字符而不改变剩余字符的相对顺序得到的新字符串。 核心思想：二维 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
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
package main

import "fmt"
import "strings" // 引入 strings 包

// max 辅助函数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// longestCommonSubsequence 最长公共子序列
func longestCommonSubsequence(text1 string, text2 string) int {
	m, n := len(text1), len(text2)

	// 1. 定义 DP 状态: dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。
	// (为了方便处理边界情况，dp 数组通常会多一行一列)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	// 2. 基本情况 (Base Cases):
	// dp[0][j] = 0 (text1 空字符串)
	// dp[i][0] = 0 (text2 空字符串)
	// Go 语言中 int 数组默认初始化为 0，所以这里无需显式设置

	// 3. 确定计算顺序并推导状态转移方程
	// 从左上到右下，逐行逐列计算
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			// 如果当前字符匹配
			if text1[i-1] == text2[j-1] { // 注意：字符串索引从 0 开始，所以是 i-1 和 j-1
				// 状态转移方程 1: 如果当前字符相同，则 LCS 长度加 1，来源于左上角对角线的值
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				// 如果当前字符不匹配
				// 状态转移方程 2: LCS 长度等于 (text1 往前一个字符的 LCS) 和 (text2 往前一个字符的 LCS) 中的较大值
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}

	// 4. 返回结果
	return dp[m][n] // dp[m][n] 即为 text1 和 text2 的 LCS 长度
}

func main() {
	fmt.Println("\n--- 最长公共子序列 ---")
	text1_1 := "abcde"
	text2_1 := "ace"
	fmt.Printf("Text1: \"%s\", Text2: \"%s\" -> LCS Length: %d\n", text1_1, text2_1, longestCommonSubsequence(text1_1, text2_1)) // 期望: 3 ("ace")

	text1_2 := "abc"
	text2_2 := "abc"
	fmt.Printf("Text1: \"%s\", Text2: \"%s\" -> LCS Length: %d\n", text1_2, text2_2, longestCommonSubsequence(text1_2, text2_2)) // 期望: 3 ("abc")

	text1_3 := "abc"
	text2_3 := "def"
	fmt.Printf("Text1: \"%s\", Text2: \"%s\" -> LCS Length: %d\n", text1_3, text2_3, longestCommonSubsequence(text1_3, text2_3)) // 期望: 0
}

示例4：0/1 背包问题 (0/1 Knapsack Problem)

问题：给定 n 件物品和一个容量为 W 的背包。每件物品有其价值 value[i] 和重量 weight[i]。每件物品只能选择一次（0/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
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
67
package main

import "fmt"

// knapsack01 解决 0/1 背包问题
func knapsack01(weights []int, values []int, W int) int {
	n := len(weights) // 物品数量

	// 1. 定义 DP 状态: dp[i][w] 表示从前 i 件物品中选择，在背包容量为 w 的情况下，所能获得的最大总价值。
	// dp 数组大小为 (n+1) * (W+1)，索引从 0 开始
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, W+1)
	}

	// 2. 基本情况 (Base Cases):
	// dp[0][w] = 0 (没有物品可选时，价值为 0)
	// dp[i][0] = 0 (背包容量为 0 时，价值为 0)
	// Go 语言中 int 数组默认初始化为 0，所以这里无需显式设置

	// 3. 确定计算顺序并推导状态转移方程
	// 遍历物品 (从 1 到 n)
	for i := 1; i <= n; i++ {
		// 遍历背包容量 (从 1 到 W)
		for w := 1; w <= W; w++ {
			// 当前物品的重量和价值 (注意：物品索引是 i-1)
			currentWeight := weights[i-1]
			currentValue := values[i-1]

			// 如果当前物品的重量大于当前背包容量 w
			if currentWeight > w {
				// 状态转移方程 1: 无法放入当前物品，最大价值等于不放入当前物品时的价值
				dp[i][w] = dp[i-1][w]
			} else {
				// 如果可以放入当前物品，有两种选择：
				// 状态转移方程 2: max(不放入当前物品, 放入当前物品)
				// 不放入：dp[i-1][w] (即当前物品的价值为 0)
				// 放入：dp[i-1][w - currentWeight] + currentValue
				// (即：放入当前物品后，背包容量减少 currentWeight，剩余容量的最大价值加上当前物品的价值)
				dp[i][w] = max(dp[i-1][w], dp[i-1][w-currentWeight]+currentValue)
			}
		}
	}

	// 4. 返回结果
	return dp[n][W] // dp[n][W] 即为所有物品在容量 W 下的最大总价值
}

func main() {
	fmt.Println("\n--- 0/1 背包问题 ---")
	// 物品：价值, 重量
	// Item 1: (60, 10)
	// Item 2: (100, 20)
	// Item 3: (120, 30)

	weights1 := []int{10, 20, 30}
	values1 := []int{60, 100, 120}
	capacity1 := 50
	fmt.Printf("Weights: %v, Values: %v, Capacity: %d -> Max Value: %d\n", weights1, values1, capacity1, knapsack01(weights1, values1, capacity1))
	// 期望: 220 (选择物品2和物品3: 100+120=220, 重量20+30=50)

	weights2 := []int{2, 3, 4, 5}
	values2 := []int{3, 4, 5, 6}
	capacity2 := 5
	fmt.Printf("Weights: %v, Values: %v, Capacity: %d -> Max Value: %d\n", weights2, values2, capacity2, knapsack01(weights2, values2, capacity2))
	// 期望: 7 (选择物品2和物品3: 3+4=7, 重量2+3=5)
}

示例5：完全 背包问题

问题描述

有 N 种物品和一个容量为 W 的背包。第 i 种物品的重量是 weights[i]，价值是 values[i]。求解将哪些物品装入背包，可使这些物品的重量总和不超过背包容量，且价值总和最大。 特点：每种物品都有无限件可用。

解题思路

与0/1背包非常相似，主要区别在于每种物品可以选取多次。

  1. 定义状态：

    • 二维 DP：dp[i][j] 表示从前 i 种物品中任意选择（每种可选多次），放入容量为 j 的背包中所能获得的最大价值。

  2. 状态转移方程： 对于第 i 种物品（对应索引 i-1）：

    • 不选择第 i 种物品：dp[i-1][j]

    • **选择第 i 种物品（前提j >= weights[i-1]**）：由于可以选多次，当我们为容量j 考虑第i 种物品时，我们可能已经为容量j - weights[i-1] 的背包选择了第i种物品。所以价值是

      1
      dp[i][j - weights[i-1]] + values[i-1]
      • 注意：这里是 dp[i][...] 而不是 dp[i-1][...]。这表示在考虑容量 j - weights[i-1] 时，仍然可以继续选择第 i 种物品。

    综合： dp[i][j] = max(dp[i-1][j], dp[i][j - weights[i-1]] + values[i-1]) (当 j >= weights[i-1] 时) dp[i][j] = dp[i-1][j] (当 j < weights[i-1] 时)

    另一种等价的思考方式是枚举第 i 种物品选 k 件： dp[i][j] = max(dp[i-1][j - k*weights[i-1]] + k*values[i-1]) for k*weights[i-1] <= j。 这个可以通过数学归纳证明与上面的转移方程等价。

  3. 初始化： 同0/1背包，dp 表格初始化为 0。

  4. 遍历顺序：

    • 外层循环遍历物品种类（i 从 1 到 N）。
    • 内层循环遍历背包容量（j 从 0 到 W）。

  5. 返回值： dp[N][W]

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package main // Assuming it's in the same package for the main_complete function

import "fmt"

// (max function is already defined above if in the same file)

// CompleteKnapsack2D 使用二维DP解决完全背包问题
func CompleteKnapsack2D(weights []int, values []int, capacity int) int {
	numItemTypes := len(weights)
	if numItemTypes == 0 || capacity == 0 {
		return 0
	}

	// dp[i][j] 表示从前 i 种物品中选取 (每种可多次)，放入容量为 j 的背包中的最大价值
	dp := make([][]int, numItemTypes+1)
	for i := range dp {
		dp[i] = make([]int, capacity+1)
	}

	// 遍历物品种类
	for i := 1; i <= numItemTypes; i++ { // i 代表考虑第 i 种物品 (对应数组索引 i-1)
		weight := weights[i-1]
		value := values[i-1]
		// 遍历背包容量
		for j := 0; j <= capacity; j++ {
			if j < weight {
				// 当前背包容量装不下这一个第 i 种物品
				dp[i][j] = dp[i-1][j]
			} else {
				// 可以选择不加入这种物品，或者加入至少一个这种物品
				// 不加入: dp[i-1][j]
				// 加入 (至少一个): dp[i][j-weight] + value
				// dp[i][j-weight] 已经考虑了第 i 种物品，所以这是正确的
				dp[i][j] = max(dp[i-1][j], dp[i][j-weight]+value)
			}
		}
	}
	return dp[numItemTypes][capacity]
}

// CompleteKnapsack1D 使用一维DP (空间优化) 解决完全背包问题
func CompleteKnapsack1D(weights []int, values []int, capacity int) int {
	numItemTypes := len(weights)
	if numItemTypes == 0 || capacity == 0 {
		return 0
	}

	// dp[j] 表示容量为 j 的背包能获得的最大价值
	dp := make([]int, capacity+1)

	// 遍历物品种类
	for i := 0; i < numItemTypes; i++ {
		weight := weights[i]
		value := values[i]
		// 遍历背包容量 (必须正序)
		// 确保物品 i 可以被多次放入。
		// 当计算 dp[j] 时，dp[j-weight] 可能已经包含了物品 i，
		// dp[j-weight] + value 意味着再多放一个物品 i。
		for j := weight; j <= capacity; j++ {
			dp[j] = max(dp[j], dp[j-weight]+value)
		}
	}
	return dp[capacity]
}

func main() { // Combined main
	// --- 0/1 Knapsack Example ---
	weights01 := []int{1, 3, 4}
	values01 := []int{15, 20, 30}
	capacity01 := 4

	fmt.Println("--- 0/1 Knapsack ---")
	fmt.Println("0/1 Knapsack (2D DP):")
	maxValue2D_01 := ZeroOneKnapsack2D(weights01, values01, capacity01)
	fmt.Printf("Max value: %d\n", maxValue2D_01) // Expected: 35

	fmt.Println("\n0/1 Knapsack (1D DP - Space Optimized):")
	maxValue1D_01 := ZeroOneKnapsack1D(weights01, values01, capacity01)
	fmt.Printf("Max value: %d\n", maxValue1D_01) // Expected: 35
	fmt.Println("----------------------")


	// --- Complete Knapsack Example ---
	weightsComplete := []int{1, 3, 4}    // 物品重量
	valuesComplete := []int{15, 20, 30} // 物品价值
	capacityComplete := 4               // 背包容量

	fmt.Println("\n--- Complete Knapsack ---")
	fmt.Println("Complete Knapsack (2D DP):")
	maxValue2DComplete := CompleteKnapsack2D(weightsComplete, valuesComplete, capacityComplete)
	// Possible combinations for capacity 4:
	// - 4x item1 (weight 1, value 15) -> total value 4*15 = 60
	// - 1x item2 (weight 3, value 20) + 1x item1 (weight 1, value 15) -> total value 20 + 15 = 35
	// - 1x item3 (weight 4, value 30) -> total value 30
	fmt.Printf("Max value: %d\n", maxValue2DComplete) // Expected: 60 (4 * item1)

	fmt.Println("\nComplete Knapsack (1D DP - Space Optimized):")
	maxValue1DComplete := CompleteKnapsack1D(weightsComplete, valuesComplete, capacityComplete)
	fmt.Printf("Max value: %d\n", maxValue1DComplete) // Expected: 60
	fmt.Println("-------------------------")
}

背包问题总结与关键区别

特性 0/1 背包 完全背包
物品限制 每件物品最多选1次 每种物品可选无限次
二维DP状态转移 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v) dp[i][j] = max(dp[i-1][j], dp[i][j-w]+v)
一维DP内循环 倒序遍历背包容量 j 正序遍历背包容量 j
核心差异原因 倒序保证 dp[j-w] 是上一轮（不含当前物品）的状态 正序允许 dp[j-w] 是本轮（已含当前物品）的状态

7. 结论

动态规划是一种强大而通用的算法设计范式，它通过识别问题的最优子结构和重叠子问题，并运用记忆化或列表法来避免重复计算，从而高效地解决许多复杂的优化问题。掌握 DP 的核心思想、通用步骤和常见题型，是提升算法能力的基石。虽然它的概念可能初看起来有些抽象，但通过大量的练习和 Go 语言的清晰实现，你会逐渐领悟其精妙之处。

#原创 #数据结构 #算法
08.算法——动态规划
https://blog.longpi1.com/2025/06/29/08-算法动态规划/