动态规划

动态规划（Dynamic Programming，DP）是算法世界中最具挑战性、也最有成就感的领域。它通过把复杂问题分解为重叠子问题、并用记忆化或表格法避免重复计算，把指数级的暴力解法优化到多项式时间。DP 的难点不在代码，而在「如何定义状态、如何写出状态转移方程」。本篇将从 DP 的核心思想讲起，给出通用的解题五步法，然后覆盖斐波那契、爬楼梯、打家劫舍、背包问题、LCS、LIS、编辑距离、矩阵路径等经典问题，最后讲解空间优化技巧和 Go 实现注意事项。掌握 DP，你将能解决一大类「最优化」和「计数」问题。

一、动态规划思想

DP 的核心是两个性质：

1. 最优子结构

一个问题的最优解，可以由其子问题的最优解构造出来。例如最短路径问题：A 到 C 的最短路径经过 B，那么 A 到 B 的部分也一定是最短路径（否则可以用更短的替换）。这就叫最优子结构。

2. 重叠子问题

在递归求解过程中，相同的子问题会被反复计算多次。例如朴素递归求斐波那契，fib(5) 会计算 fib(3) 两次、fib(2) 三次。DP 通过记忆化（自顶向下）或表格法（自底向上）避免这种重复计算。

DP 与分治的区别：分治的子问题相互独立（如归并排序），DP 的子问题重叠。DP 与贪心的区别：贪心做出局部最优选择后不回头，DP 会枚举所有选择取最优。

二、解题步骤

解 DP 题有一套通用流程，建议严格按步骤训练：

定义状态：用 dp[i] 或 dp[i][j] 表示什么？状态的定义直接决定转移方程的写法。常见有「以 i 结尾的最优值」「前 i 个物品的最优值」「区间 [i,j] 上的最优值」。
写出状态转移方程：dp[i] 由哪些子状态推出？这一步是 DP 的灵魂，需要画图、举小例子辅助思考。
确定初始条件：dp[0]、dp[1] 等基础情况的值。边界处理错误是 DP 题最常见的 bug。
确定计算顺序：保证计算 dp[i] 时它依赖的子状态已算好。一维通常从左到右，二维可能要按行、按列、或按区间长度。
空间优化：若 dp[i] 只依赖前几个状态，可把二维压成一维、一维压成几个变量。

三、经典问题

1. 斐波那契数列

最简单的 DP 入门：fib(n) = fib(n-1) + fib(n-2)。

package main

import "fmt"

// 朴素递归：O(2^n)，重叠子问题导致爆炸
func fibRec(n int) int {
	if n <= 1 {
		return n
	}
	return fibRec(n-1) + fibRec(n-2)
}

// 记忆化递归（自顶向下）：O(n)
func fibMemo(n int) int {
	memo := make([]int, n+1)
	for i := range memo {
		memo[i] = -1
	}
	var dfs func(int) int
	dfs = func(k int) int {
		if k <= 1 {
			return k
		}
		if memo[k] != -1 {
			return memo[k]
		}
		memo[k] = dfs(k-1) + dfs(k-2)
		return memo[k]
	}
	return dfs(n)
}

// 动态规划（自底向上）：O(n) 时间，O(n) 空间
func fibDP(n int) int {
	if n <= 1 {
		return n
	}
	dp := make([]int, n+1)
	dp[0], dp[1] = 0, 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

// 空间优化：只存前两个变量，O(1) 空间
func fibOpt(n int) int {
	if n <= 1 {
		return n
	}
	prev, cur := 0, 1
	for i := 2; i <= n; i++ {
		prev, cur = cur, prev+cur
	}
	return cur
}

func main() {
	for _, n := range []int{10, 20, 30} {
		fmt.Printf("fib(%d): memo=%d dp=%d opt=%d\n",
			n, fibMemo(n), fibDP(n), fibOpt(n))
	}
}

2. 爬楼梯（LC 70）

题目：每次能爬 1 或 2 阶，爬到第 n 阶有多少种方法？

思路：到第 i 阶的方法数 = 到 i-1 阶的方法数 + 到 i-2 阶的方法数（最后一步要么跨 1 阶、要么跨 2 阶）。转移方程和斐波那契完全一致。

package main

import "fmt"

func climbStairs(n int) int {
	if n <= 2 {
		return n
	}
	prev, cur := 1, 2
	for i := 3; i <= n; i++ {
		prev, cur = cur, prev+cur
	}
	return cur
}

func main() {
	for _, n := range []int{2, 3, 5, 10} {
		fmt.Printf("爬 %d 阶: %d 种方法\n", n, climbStairs(n))
	}
}

3. 打家劫舍（LC 198）

题目：沿街排列的房屋各有金额，不能偷相邻两间，求最大金额。

思路：dp[i] 表示前 i 间房能偷的最大金额。对第 i 间，要么不偷（dp[i-1]），要么偷（dp[i-2] + nums[i]），取较大。

package main

import "fmt"

func rob(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	if n == 1 {
		return nums[0]
	}
	prev2, prev1 := nums[0], max(nums[0], nums[1])
	for i := 2; i < n; i++ {
		prev2, prev1 = prev1, max(prev1, prev2+nums[i])
	}
	return prev1
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	fmt.Println("打家劫舍 [1,2,3,1]:", rob([]int{1, 2, 3, 1}))       // 4
	fmt.Println("打家劫舍 [2,7,9,3,1]:", rob([]int{2, 7, 9, 3, 1})) // 12
}

4. 0-1 背包问题

题目：有 n 个物品，每个有重量 w[i] 和价值 v[i]，背包容量 W，每件物品最多选一次，求最大价值。

思路：dp[i][j] 表示前 i 件物品、容量 j 时的最大价值。转移：不选第 i 件 dp[i-1][j]，或选 dp[i-1][j-w[i]] + v[i]。

package main

import "fmt"

func knapsack01(weights, values []int, capacity int) int {
	n := len(weights)
	// dp[i][j]：前 i 件物品、容量 j 的最大价值
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, capacity+1)
	}
	for i := 1; i <= n; i++ {
		for j := 0; j <= capacity; j++ {
			dp[i][j] = dp[i-1][j] // 不选第 i 件
			if j >= weights[i-1] {
				dp[i][j] = max(dp[i][j], dp[i-1][j-weights[i-1]]+values[i-1])
			}
		}
	}
	return dp[n][capacity]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	weights := []int{2, 3, 4, 5}
	values := []int{3, 4, 5, 6}
	fmt.Println("0-1 背包容量 5:", knapsack01(weights, values, 5)) // 7
}

5. 完全背包

每件物品可以选无限次。转移方程只需把 dp[i-1][j-w[i]] 改成 dp[i][j-w[i]]（同一行内转移，表示可重复选）。

package main

import "fmt"

func completeKnapsack(weights, values []int, capacity int) int {
	n := len(weights)
	dp := make([]int, capacity+1)
	for i := 0; i < n; i++ {
		for j := weights[i]; j <= capacity; j++ {
			dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
		}
	}
	return dp[capacity]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	weights := []int{1, 3, 4}
	values := []int{15, 20, 30}
	fmt.Println("完全背包容量 4:", completeKnapsack(weights, values, 4)) // 60
}

一维优化时，0-1 背包容量需逆序遍历（避免一件物品被选多次），完全背包容量需正序遍历（允许重复选）。这是背包问题的核心细节。

6. 最长公共子序列（LCS）

题目：两个字符串的最长公共子序列长度。

思路：dp[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符的 LCS。若 s1[i-1]==s2[j-1]，dp[i][j]=dp[i-1][j-1]+1；否则 dp[i][j]=max(dp[i-1][j], dp[i][j-1])。

package main

import "fmt"

func longestCommonSubsequence(s1, s2 string) int {
	m, n := len(s1), len(s2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return dp[m][n]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	fmt.Println("LCS abcde/ace:", longestCommonSubsequence("abcde", "ace")) // 3
	fmt.Println("LCS abc/abc:", longestCommonSubsequence("abc", "abc"))     // 3
}

7. 最长递增子序列（LIS）

题目：数组的最长严格递增子序列长度。

思路一：O(n²) DP。dp[i] 表示以 nums[i] 结尾的 LIS 长度，对每个 j < i 若 nums[j]<nums[i] 则 dp[i]=max(dp[i], dp[j]+1)。

package main

import "fmt"

func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	n := len(nums)
	dp := make([]int, n)
	for i := range dp {
		dp[i] = 1
	}
	maxLen := 1
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] && dp[j]+1 > dp[i] {
				dp[i] = dp[j] + 1
			}
		}
		if dp[i] > maxLen {
			maxLen = dp[i]
		}
	}
	return maxLen
}

func main() {
	fmt.Println("LIS [10,9,2,5,3,7,101,18]:",
		lengthOfLIS([]int{10, 9, 2, 5, 3, 7, 101, 18})) // 4
}

思路二：O(n log n) 贪心 + 二分。维护一个 tails 数组，tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素。新元素用二分找到第一个 ≥ 它的位置替换。

package main

import (
	"fmt"
	"sort"
)

func lengthOfLISBinary(nums []int) int {
	var tails []int
	for _, v := range nums {
		// 找第一个 >= v 的位置
		idx := sort.Search(len(tails), func(i int) bool {
			return tails[i] >= v
		})
		if idx == len(tails) {
			tails = append(tails, v)
		} else {
			tails[idx] = v
		}
	}
	return len(tails)
}

func main() {
	fmt.Println("LIS(二分) [10,9,2,5,3,7,101,18]:",
		lengthOfLISBinary([]int{10, 9, 2, 5, 3, 7, 101, 18})) // 4
}

8. 编辑距离（LC 72）

题目：把 word1 转换成 word2 所需的最少操作次数（插入、删除、替换）。

思路：dp[i][j] 表示 word1 前 i 字符转成 word2 前 j 字符的最少操作。若字符相等 dp[i][j]=dp[i-1][j-1]；否则取「删、插、替」三者最小 +1。

package main

import "fmt"

func minDistance(word1, word2 string) int {
	m, n := len(word1), len(word2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][0] = i // word1 前 i 个变成空串需删 i 次
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j // 空串变成 word2 前 j 个需插 j 次
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = min3(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
			}
		}
	}
	return dp[m][n]
}

func min3(a, b, c int) int {
	m := a
	if b < m {
		m = b
	}
	if c < m {
		m = c
	}
	return m
}

func main() {
	fmt.Println("编辑距离 horse/ros:", minDistance("horse", "ros"))     // 3
	fmt.Println("编辑距离 intention/execution:", minDistance("intention", "execution")) // 5
}

9. 矩阵路径问题

最小路径和（LC 64）：从左上到右下，每次只能向右或向下，求路径最小和。

package main

import "fmt"

func minPathSum(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	dp[0][0] = grid[0][0]
	for i := 1; i < m; i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for j := 1; j < n; j++ {
		dp[0][j] = dp[0][j-1] + grid[0][j]
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if dp[i-1][j] < dp[i][j-1] {
				dp[i][j] = dp[i-1][j] + grid[i][j]
			} else {
				dp[i][j] = dp[i][j-1] + grid[i][j]
			}
		}
	}
	return dp[m-1][n-1]
}

func main() {
	grid := [][]int{
		{1, 3, 1},
		{1, 5, 1},
		{4, 2, 1},
	}
	fmt.Println("最小路径和:", minPathSum(grid)) // 7
}

四、空间优化技巧

1. 滚动数组

当 dp[i] 只依赖 dp[i-1]（或前几行），可以用「滚动数组」：用 dp[i%2] 代替 dp[i]，把二维空间压到两行。

package main

import "fmt"

// 0-1 背包空间优化：二维压成一维
func knapsack01Opt(weights, values []int, capacity int) int {
	n := len(weights)
	dp := make([]int, capacity+1)
	// 逆序遍历容量，保证每件物品只选一次
	for i := 0; i < n; i++ {
		for j := capacity; j >= weights[i]; j-- {
			if dp[j-weights[i]]+values[i] > dp[j] {
				dp[j] = dp[j-weights[i]] + values[i]
			}
		}
	}
	return dp[capacity]
}

func main() {
	weights := []int{2, 3, 4, 5}
	values := []int{3, 4, 5, 6}
	fmt.Println("0-1 背包优化:", knapsack01Opt(weights, values, 5)) // 7
}

2. 一维 DP / 变量替换

如斐波那契、爬楼梯、打家劫舍，只需前两个状态，用两个变量即可。前面的示例已展示。

五、Go 实现注意事项

1. 切片初始化

Go 中切片必须显式初始化长度，否则访问会 panic。DP 表常用 make([][]int, m+1) + 内层 make([]int, n+1)。也可以用 make([]int, n+1) 一次性分配再切片，减少内存分配次数。

package main

import "fmt"

// 高效初始化二维 DP 表
func newDP(m, n int) [][]int {
	// 一次性分配 m*n 的连续内存
	data := make([]int, m*n)
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = data[i*n : (i+1)*n]
	}
	return dp
}

func main() {
	dp := newDP(3, 4)
	dp[1][2] = 5
	fmt.Println("dp[1][2]:", dp[1][2])
	fmt.Println("初始化完成:", dp)
}

2. 内存优化

大规模 DP 优先用一维优化。
若只需最终结果，可及时释放中间行（用滚动数组）。
注意 Go 的逃逸分析：大数组分配在堆上，可能增加 GC 压力。

3. 避免常见陷阱

边界处理：dp[0][0]、空输入、单元素输入要单独考虑。
计算顺序：依赖关系决定遍历顺序，区间 DP 通常按长度递增。
状态定义模糊：先明确「dp[i] 代表什么」，再写转移方程。

六、LeetCode 经典题汇总

1. 零钱兑换（LC 322）

题目：给定硬币面额和金额，求凑成该金额的最少硬币数。

思路：完全背包变形。dp[i] 表示金额 i 的最少硬币数，dp[i] = min(dp[i-coin]) + 1。

package main

import (
	"fmt"
	"math"
)

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	for i := range dp {
		dp[i] = math.MaxInt32
	}
	dp[0] = 0
	for i := 1; i <= amount; i++ {
		for _, c := range coins {
			if c <= i && dp[i-c]+1 < dp[i] {
				dp[i] = dp[i-c] + 1
			}
		}
	}
	if dp[amount] == math.MaxInt32 {
		return -1
	}
	return dp[amount]
}

func main() {
	fmt.Println("零钱兑换 [1,2,5] amount=11:", coinChange([]int{1, 2, 5}, 11)) // 3
}

2. 最长回文子串（LC 5）

题目：返回字符串中最长回文子串。

思路：区间 DP。dp[i][j] 表示 s[i..j] 是否回文。dp[i][j] = (s[i]==s[j]) && dp[i+1][j-1]。

package main

import "fmt"

func longestPalindrome(s string) string {
	n := len(s)
	if n < 2 {
		return s
	}
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}
	start, maxLen := 0, 1
	// 单字符都是回文
	for i := 0; i < n; i++ {
		dp[i][i] = true
	}
	// 按长度递增枚举
	for l := 2; l <= n; l++ {
		for i := 0; i+l-1 < n; i++ {
			j := i + l - 1
			if s[i] == s[j] {
				if l == 2 || dp[i+1][j-1] {
					dp[i][j] = true
					if l > maxLen {
						start = i
						maxLen = l
					}
				}
			}
		}
	}
	return s[start : start+maxLen]
}

func main() {
	fmt.Println("最长回文子串 babad:", longestPalindrome("babad")) // bab 或 aba
	fmt.Println("最长回文子串 cbbd:", longestPalindrome("cbbd"))   // bb
}

七、复杂度分析

DP 的复杂度 = 状态数 × 每个状态的转移代价。

问题	状态数	转移代价	总时间	空间（优化后）
斐波那契/爬楼梯	n	O(1)	O(n)	O(1)
打家劫舍	n	O(1)	O(n)	O(1)
0-1 背包	n×W	O(1)	O(nW)	O(W)
完全背包	n×W	O(1)	O(nW)	O(W)
LCS	m×n	O(1)	O(mn)	O(min(m,n))
LIS（DP）	n	O(n)	O(n²)	O(n)
LIS（二分）	n	O(log n)	O(n log n)	O(n)
编辑距离	m×n	O(1)	O(mn)	O(min(m,n))
最小路径和	m×n	O(1)	O(mn)	O(n)

八、小结

动态规划是算法学习的「深水区」，本篇要点：

两大性质：最优子结构（最优解由子问题最优解构造）+ 重叠子问题（子问题被反复计算）。DP 用记忆化或表格法消除重复计算。
解题五步：定义状态 → 写转移方程 → 确定初始条件 → 确定计算顺序 → 空间优化。其中转移方程是灵魂，建议画图、举小例子辅助。
经典模型：
- 一维线性：斐波那契、爬楼梯、打家劫舍。
- 背包：0-1（逆序遍历容量）、完全（正序遍历容量）。
- 双串：LCS、编辑距离。
- 子序列：LIS（O(n²) DP 或 O(n log n) 贪心+二分）。
- 区间：最长回文子串（按长度递增枚举）。
- 矩阵路径：最小路径和。
空间优化：滚动数组（dp[i%2]）、一维压缩（背包）、变量替换（斐波那契）。注意压缩后遍历顺序可能要变。
Go 注意：切片必须显式初始化长度；大规模 DP 优先一维优化减少 GC 压力；边界和计算顺序是常见 bug 来源。
复杂度：状态数 × 转移代价。优化往往从减少状态数（如 LIS 二分）或降低转移代价（如单调队列优化 DP）入手。

DP 的学习没有捷径，唯有刷题积累「模式识别」能力。建议从斐波那契、爬楼梯入门，逐步过渡到背包、LCS、编辑距离，最后挑战区间 DP、状压 DP、树形 DP。每道题都要先自己想状态定义和转移方程，再看题解，这样才有真正的提升。

至此，Go 数据结构与算法系列十篇全部结束。从复杂度分析到数组、链表、栈队列、哈希表、树、堆、图、排序、动态规划，我们覆盖了面试和工程中最核心的数据结构与算法。希望这个系列能成为你面试备考和日常工作的参考手册。算法学习是一场马拉松，坚持练习，量变终会引起质变。

入门篇

进阶篇

资深篇

动态规划

一、动态规划思想

1. 最优子结构

2. 重叠子问题

二、解题步骤

三、经典问题

1. 斐波那契数列

2. 爬楼梯（LC 70）

3. 打家劫舍（LC 198）

4. 0-1 背包问题

5. 完全背包

6. 最长公共子序列（LCS）

7. 最长递增子序列（LIS）

8. 编辑距离（LC 72）

9. 矩阵路径问题

四、空间优化技巧

1. 滚动数组

2. 一维 DP / 变量替换

五、Go 实现注意事项

1. 切片初始化

2. 内存优化

3. 避免常见陷阱

六、LeetCode 经典题汇总

1. 零钱兑换（LC 322）

2. 最长回文子串（LC 5）

七、复杂度分析

八、小结

动态规划 ​

一、动态规划思想 ​

1. 最优子结构 ​

2. 重叠子问题 ​

二、解题步骤 ​

三、经典问题 ​

1. 斐波那契数列 ​

2. 爬楼梯（LC 70） ​

3. 打家劫舍（LC 198） ​

4. 0-1 背包问题 ​

5. 完全背包 ​

6. 最长公共子序列（LCS） ​

7. 最长递增子序列（LIS） ​

8. 编辑距离（LC 72） ​

9. 矩阵路径问题 ​

四、空间优化技巧 ​

1. 滚动数组 ​

2. 一维 DP / 变量替换 ​

五、Go 实现注意事项 ​

1. 切片初始化 ​

2. 内存优化 ​

3. 避免常见陷阱 ​

六、LeetCode 经典题汇总 ​

1. 零钱兑换（LC 322） ​

2. 最长回文子串（LC 5） ​

七、复杂度分析 ​

八、小结 ​

动态规划

一、动态规划思想

1. 最优子结构

2. 重叠子问题

二、解题步骤

三、经典问题

1. 斐波那契数列

2. 爬楼梯（LC 70）

3. 打家劫舍（LC 198）

4. 0-1 背包问题

5. 完全背包

6. 最长公共子序列（LCS）

7. 最长递增子序列（LIS）

8. 编辑距离（LC 72）

9. 矩阵路径问题

四、空间优化技巧

1. 滚动数组

2. 一维 DP / 变量替换

五、Go 实现注意事项

1. 切片初始化

2. 内存优化

3. 避免常见陷阱

六、LeetCode 经典题汇总

1. 零钱兑换（LC 322）

2. 最长回文子串（LC 5）

七、复杂度分析

八、小结