计算机基础

引言 (Introduction)

动态规划（Dynamic Programming, DP）是算法设计中最强大的方法论之一。如果说贪心算法是"只看眼前"的闪电战，动态规划则是"通盘考虑"的持久战——它通过系统性地枚举子问题并复用答案，在指数级的搜索空间中高效地找到最优解。

DP 的学习难度不在于单个知识点，而在于状态定义的建模能力。同样一道题，不同的状态定义可能导致从天差地别的复杂度。本文是本系列第一篇，聚焦于 DP 的理论基础与最基础的一维状态建模模式。

1. DP 的理论基础

1.1 最优子结构

一个问题具有最优子结构，当且仅当原问题的最优解可以由子问题的最优解组合而成。这是 DP 和贪心的共同前提。

形式化定义：设原问题 $P$ 的最优解为 $OPT(P)$。$P$ 可分解为子问题 $P_1, P_2, \ldots, P_k$。若存在函数 $f$ 使得：

$$OPT(P) = f(OPT(P_1), OPT(P_2), \ldots, OPT(P_k))$$

则称 $P$ 具有最优子结构。

1.2 重叠子问题

这是 DP 区别于分治的关键特征。在分治（如归并排序）中，子问题互不重叠；而在 DP 中，同一个子问题会被多次递归遇到。如果不缓存（memoize），将产生指数级的重复计算。

以斐波那契数列为例：

              fib(5)
           /          \
      fib(4)          fib(3)
     /      \        /      \
  fib(3)   fib(2)  fib(2)  fib(1)
  /    \
fib(2) fib(1)

fib(3) 被计算了 2 次，fib(2) 被计算了 3 次。随着 $n$ 增大，重复计算呈指数增长。DP 用一个数组存储中间结果，将复杂度从 $O(2^n)$ 降到 $O(n)$。

1.3 状态与状态转移方程

DP 的核心是定义「状态」和「转移」：

  • 状态（State）：用一组变量描述当前子问题的全貌。例如 $dp[i]$ 表示「考虑到第 $i$ 个元素时的最优解」。
  • 状态转移方程（State Transition）：描述当前状态如何由更小的状态推导而来。
  • 边界条件（Base Case）：最小子问题的答案。

识别 DP 问题的三个信号：

  1. 问「最大/最小/最优」（最值问题）。
  2. 问「方案数/路径数」（计数问题）。
  3. 决策存在后效性，但可以通过增加状态维度消除（状态升维）。

1.4 贪心 vs DP 的再度辨析

承接贪心系列的讨论，这里给出更精确的对比：

条件 贪心 DP
最优子结构 需要 需要
重叠子问题 不需要 需要
贪心选择性质 必须 不需要
决策是否可以撤销 不可撤销 枚举所有可能性

判断流程：一个问题先看能否贪心（效率最优），不能则考虑 DP。如果连最优子结构都没有，那就只能是回溯暴力搜索。

2. 两种实现范式

2.1 自顶向下：记忆化搜索（Memoization）

从原问题出发，递归分解子问题。遇到已计算过的状态直接返回缓存结果。

from functools import lru_cache
from typing import List

def fib_memo(n: int) -> int:
    """记忆化递归求斐波那契第 n 项"""

    @lru_cache(maxsize=None)
    def dp(i: int) -> int:
        if i <= 1:
            return i
        return dp(i - 1) + dp(i - 2)

    return dp(n)

优点：只计算需要的状态（懒求值），思维与递归一致。 缺点：递归栈开销，可能有栈溢出风险。

2.2 自底向上：递推填表（Tabulation）

从小问题开始，按顺序填表，直到推出原问题的答案。

from typing import List

def fib_tab(n: int) -> int:
    """递推填表求斐波那契第 n 项"""
    if n <= 1:
        return n
    dp: List[int] = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

优点：无递归开销，容易做空间优化（滚动数组）。 缺点：必须计算所有子问题（可能计算不需要的状态）。

原则：面试 / 竞赛中优先使用递推填表——代码更短、不易栈溢出。思维阶段可以用记忆化辅助推导转移方程。

3. 一维 DP 的三种基础模式

3.1 模式一：线性递推

状态只依赖前一个或前几个位置的固定索引，转移方向单一。

典型方程：$dp[i] = f(dp[i-1], dp[i-2], \ldots, nums[i])$

3.2 模式二：环形 DP

数组首尾相连，第一个和最后一个元素产生新的约束。解决套路：跑两次线性 DP，一次不选首，一次不选尾，取最大值。

3.3 模式三：状态机 DP

在每个位置有多个可能状态（如「持有」「不持有」），状态之间的转移构成有限状态机。

下面通过三道 LeetCode 题目逐一展开。

4. LeetCode 53：最大子数组和

题目：给定整数数组 nums，找出具有最大和的连续子数组，返回其和。

这是 DP 的入门经典。设 $dp[i]$ 表示以 $i$ 结尾的最大子数组和。转移方程：

$$dp[i] = \max(nums[i],\ dp[i-1] + nums[i])$$

即要么自己另起一段，要么接在前面的段后面。

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp: List[int] = [0] * n
        dp[0] = nums[0]
        ans = dp[0]

        for i in range(1, n):
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
            ans = max(ans, dp[i])

        return ans

空间优化（Kadane 算法）：$dp[i]$ 只依赖 $dp[i-1]$，可以用一个变量代替整个数组：

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur_max = nums[0]
        ans = nums[0]

        for i in range(1, len(nums)):
            cur_max = max(nums[i], cur_max + nums[i])
            ans = max(ans, cur_max)

        return ans

复杂度：时间 $O(n)$，空间 $O(1)$。

关键洞察：状态定义的「以 $i$ 结尾」是 DP 建模的核心技巧——通过给状态附加一个约束（连续性），使得转移方程可以被精确写出。最终答案是在所有 $dp[i]$ 中取最大值。

5. LeetCode 198：打家劫舍

题目：沿街房屋，每家有钱 nums[i]。不能偷相邻两家，求最大收益。

这是状态机 DP 的入门题。定义两个状态：

  • $dp[i][0]$：不偷第 $i$ 家的最大收益。
  • $dp[i][1]$：偷第 $i$ 家的最大收益。

转移方程：

$$dp[i][0] = \max(dp[i-1][0], dp[i-1][1])$$$$dp[i][1] = dp[i-1][0] + nums[i]$$

不偷 → 可以从前一家的任何状态转移来。偷 → 必须前一家的「不偷」状态。

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i][0] = 不偷 i, dp[i][1] = 偷 i
        dp0, dp1 = 0, nums[0]          # 滚动变量替代二维数组

        for i in range(1, n):
            new_dp0 = max(dp0, dp1)
            new_dp1 = dp0 + nums[i]
            dp0, dp1 = new_dp0, new_dp1

        return max(dp0, dp1)

复杂度：时间 $O(n)$，空间 $O(1)$。

另一种视角：设 $dp[i]$ = 考虑前 $i$ 家的最大收益。转移：$dp[i] = \max(dp[i-1], dp[i-2] + nums[i])$。即要么不偷第 $i$ 家（沿用 $dp[i-1]$），要么偷第 $i$ 家（跳过第 $i-1$ 家，从 $dp[i-2]$ 转移来）。这个一维方程等价于上述状态机，但状态机的可扩展性更好（如后续加入更多约束）。

6. LeetCode 213：打家劫舍 II

题目：198 的环形版本——第一个和最后一个房屋相邻。

环形问题的通用解法：破环为线。首尾不能同时偷，于是分解为两个子问题：

  1. 不偷第一家：对 nums[1:] 跑 198 的解法。
  2. 不偷最后一家：对 nums[:-1] 跑 198 的解法。
  3. 取两者最大值。特例：$n=1$ 时直接返回 nums[0]。
from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]

        def rob_linear(arr: List[int]) -> int:
            dp0, dp1 = 0, arr[0]
            for i in range(1, len(arr)):
                new_dp0 = max(dp0, dp1)
                new_dp1 = dp0 + arr[i]
                dp0, dp1 = new_dp0, new_dp1
            return max(dp0, dp1)

        return max(rob_linear(nums[1:]),   # 不偷第一家
                   rob_linear(nums[:-1]))  # 不偷最后一家

复杂度：时间 $O(n)$，空间 $O(1)$。

环形 DP 的通用模板：

环形问题 → 固定第一个元素选/不选 → 拆成两个线性问题 → 取最值

7. 一维 DP 的建模总结

回顾三道题的状态定义与转移方程：

题目 状态定义 转移方程 模式
53 最大子数组和 $dp[i]$：以 $i$ 结尾的最大和 $dp[i] = \max(nums[i], dp[i-1] + nums[i])$ 线性递推
198 打家劫舍 $dp[i][0/1]$：不偷/偷第 $i$ 家 状态机转移（两方程） 状态机
213 打家劫舍 II 同 198 + 环形处理 跑两次 198 环形 → 线性

核心建模流程：

  1. 确定状态代表的决策阶段（“考虑到第 $i$ 个元素”）。
  2. 确定状态的约束条件（“以 $i$ 结尾”、“是否偷 $i$"）。
  3. 写出转移方程——当前状态能由哪些小状态推导。
  4. 确定边界条件。
  5. 考虑空间优化（滚动变量 / 滚动数组）。

结论 (Conclusion)

本文建立了 DP 的理论基础（最优子结构、重叠子问题）和一维 DP 的三种基础建模模式（线性递推、环形、状态机）。三道题（53、198、213）的目标不是题海，而是让你体会到状态定义的艺术性——同一个问题可以有多种定义方式，而好的定义才能导出简洁的转移方程。

下一篇预览：二维 DP 与网格问题——当状态需要两个维度来描述时，转移方程如何设计？我们将学习路径计数、最小路径和、最大正方形，以及如何从填好的 DP 表中反向追踪出最优路径（LeetCode 62、64、221）。