动态规划

作于：2025-06-20 20:49 ，预计阅读时间 5 分钟

周三的面试被问了动态规划，明天要二面所以再临场补一下课。

动态规划的基本理念是把大问题分解成小的子问题进行计算，重新汇总成大问题的解。区别于一般的分治法，动态规划面对的问题往往存在重复的子问题。

递归搜索

以上周面试的那个题为例，一次跨1级或2级台阶，n级台阶有几种爬法。暴力法是递归搜索：

func solution(n int) int {
  // 只剩1级的时候只有一种方案，剩2级时只有两种方案：2,1-1
  if n == 1 || n == 2 {
    return n
  }
  return solution(n-1)+solution(n-2)
}

89

如果我们打印出每次递归的n值，会发现有重复的n被计算。我添加一个全局map来记录n被计算的次数。

func solution(n int) int {
	// 统计n被计算的次数
	counter[n] += 1

  // 只剩1级的时候只有一种方案，剩2级时只有两种方案：2,1-1
  if n == 1 || n == 2 {
    return n
  }
  return solution(n-1)+solution(n-2)
}

10: 1
8: 2
7: 3
6: 5
5: 8
4: 13
3: 21
2: 34
9: 1
1: 21

暴力搜索的策略实际是遍历了这样一棵树，数出有效节点数量。

graph TD
    A[3] --"跨1级"--> B[2]
    A --"跨2级"--> C[1]
    B --"跨1级"--> D[1]

备忘录

显然暴力搜索会计算大量重复子问题，一个最直观的策略就是引入一个小备忘本，在计算过一次问题后记录下来，下次遇到时就不需要再递归计算一遍。

func solution2(n int, memo map[int]int) int {
	if memo[n] != 0 {
		return memo[n]
	}

	counter[n] += 1
	// 只剩1级的时候只有一种方案，剩2级时只有两种方案：2,1-1
	if n == 1 || n == 2 {
		memo[n] = n
		return n
	}
	memo[n] = solution2(n-1, memo) + solution2(n-2, memo)
	return memo[n]
}

89
3: 1
8: 1
6: 1
4: 1
2: 1
1: 1
10: 1
9: 1
7: 1
5: 1

就是这样。暴力法的内核是分治，将大问题拆分成小问题直到能被容易的解决。

动态规划

上面的备忘录法也有叫做自顶向下的动态规划的。自顶向下的方法从原问题 n 出发，把问题逐步拆分到最小单元，求解顺序是 f(n),f(n-1),...,f(2),f(1)。

另一种叫做制表法的动态规划算法则是自底向上，从较小规模的问题开始，求解顺序是 f(1),f(2),...,f(n) 。

func solution3(n int) int {
	// 对最小已知问题，选择短路返回
	if n == 1 || n == 2 {
		return n
	}

	// 每个子问题解的数组
	dp := make([]int, n+1)
	// 初始化最小已知问题
	dp[0] = 0
	dp[1] = 1
	dp[2] = 2
	// 迭代计算稍大规模的子问题，直到求解出原问题 f(n)
	for i := 3; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

针对这个爬台阶问题，每个f(n)其实都只依赖f(n-1)和f(n-2)的解，所以dp实际上只需要2格就够用了。

最终可以优化为这样：

func solution3(n int) int {
	// 对最小已知问题，选择短路返回
	if n == 1 || n == 2 {
		return n
	}

	// 每一步计算依赖的子问题解，初始化为最小子问题解
	var (
		a int = 1 // f(1)
		b int = 2 // f(2)
	)
	// 迭代计算
	for i := 3; i <= n; i++ {
		// 迭代前，a=f(i-2),b=f(i-1)
		a, b = b, a+b
		// 迭代后，a=f(i-1),b=f(i)
	}
  // 迭代结束后，b=f(n)
	return b
}

最优子结构

动态规划算法还可以进一步延伸为求解最优子结构。修改之前的问题：

现在有 n 级台阶，你可以一次跨1级台阶或2级台阶，每级台阶要付出不同的代价 cost[n]，求解踩上第n级台阶的最小代价。

同样的，我们先自顶向下去拆分子问题，在第 n 级台阶需要付出的总代价是 previous_minimum_cost + cost[n]，在第 n 级台阶求解最小化代价，我们只能从两种上一步决策里选择，也就是从 n-1 和 n-2 的总代价里取较小的那个。

也就是设f(n)是上到第n级台阶的最小总代价，f可以定义为f(n) = min(f(n-1), f(n-2)) + cost[n]。

f(n) 的最小子问题是 f(1)=cost[1]，f(2)=cost[2] 。为什么 f(2)=cost[2]，是因为另一个策略（1级+1级）的cost是cost[1]+cost[2]，肯定是小于cost[2]的。

func solution1(cost []int,memo map[int]int) int {
	n := len(cost)
	if n == 0 {
		return 0
	} else if n == 1 || n == 2 {
		return cost[n-1]
	}

	if memo[n] != 0 {
		return memo[n]
	}

	return min(solution1(cost[:n-1]), solution1(cost[:n-2])) + cost[n-1]
}

反过来用自底向上分析就是：

func solution2(cost []int) int {
	n := len(cost)
	if n == 0 {
		return 0
	} else if n == 1 || n == 2 {
		return cost[n-1]
	}

	dp := make([]int, n)
	dp[0] = cost[0]
	dp[1] = cost[1]

	for i := 2; i < n; i++ {
		dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
	}

	return dp[n-1]
}

同样的，因为问题只依赖前两个子问题的解，dp也可以被优化成两格。

总结

动态规划适合的领域是问题可以被拆分为更小的子问题求解，原问题依赖于子问题的解，拆分中会出现重叠子问题的场合。

听起来简单，但是考虑的条件变多的时候拆子问题就会比较头大，0/1背包一时还啃不下来，已经花了2小时20分了。

明天面试完再看看。

/go/ /动态规划/