1. 动态规划到底是什么？
1.1 概念与直觉
动态规划是一种<系统化分解问题的方法，通过将一个复杂问题拆分为若干简单子问题来求解。它的核心在于子问题的复用，避免对同一个子问题重复计算，从而提升效率。
与单纯的递归相比，动态规划通过对<状态空间的记忆化，或将解存放在表中实现自底向上求解，从而将指数级复杂度降到多项式甚至线性级别的时间复杂度。最优子结构与无后效性是其重要特征。
从宏观角度看，动态规划的目标是把一个全局最优解转化为对若干局部最优解的组合，确保每一步的选择都能最大化（或最小化）最终结果。
1.2 与递归的关系
动态规划本质上是对递归思想的强化与优化。通过记忆化搜索，我们在首次计算一个子问题时将结果保存，后续遇到相同子问题就直接返回已缓存的值。
也可以把动态规划理解为把问题转化为状态转移的网格，每一个状态代表一个子问题的解，状态转移则描述如何通过前一状态得到下一状态。这样既能利用重复子结构，又能系统地构建解的过程。
2. DP 的核心设计与实现要点
2.1 状态的定义与选择
在 DP 中，第一步是定义状态，也就是把问题抽象成一个或多个下标的组合，能够唯一描述一个子问题。一个良好的状态应具备<无歧义性、可计算性与可转移性。
常见的状态定义包括对行列、对长度、对前缀等的刻画。不恰当的状态定义会导致冗余计算或边界困难，因此需要在设计阶段反复推敲。
2.2 状态转移方程与边界条件
确定状态后，需要给出状态转移方程，即如何从一个或多个前驱状态推导出当前状态的最优解。转移方程往往体现了问题的约束和优化目标。边界条件则提供了初始解，确保从可行的起点向前推进。边界处理正确性决定了题解的正确性。
一个清晰的转移范式是：当前位置的最优解等于其前一状态的最优解的某种组合，再加上当前状态的贡献。通过这种结构，我们可以用“自顶向下”或“自底向上”两种方式实现。两种实现路径各有适用场景。
2.3 自顶向下 vs 自底向上
自顶向下（记忆化搜索）适合先定义问题再逐步求解，代码往往更接近自然思路，便于初学者理解。 memoization把已经解决的子问题结果缓存起来，用于后续调用。
自底向上（迭代填表）则直接从最小的子问题开始，逐步构建到最终解。它通常<不需要递归，并且易于对时间和空间进行严格控制，能更好地进行空间优化。模板化实现往往更高效稳定。
3. DP 题解的完整步骤
3.1 将问题抽象成状态与转移
完整的 DP 题解始于对问题的状态抽象，需要把原问题转化为一组离散的状态，确保同一状态只对应一个最优解。这一过程是 DP 的核心设计步骤之一。
在抽象阶段，应关注问题的约束、容量、目标函数等要素，以确保状态能覆盖所有可能的子问题。避免状态过多或重复定义，否则会影响效率与可维护性。
3.2 设定边界与初始值
边界条件定义了 DP 的起始点与结束点，通常是最小粒度的子问题。初始值正确性是后续转移正确性的前提。没有恰当的边界，整个表格或记忆结构都会失去方向。
明确地写出边界，如当某个索引越界、或达到最小/最大状态时的返回值，是实现稳定 DP 的关键。边界条件往往决定算法的鲁棒性。
3.3 枚举或合并的递推方向
在确定状态后，需要明确对每个状态的可选操作集合，以及从哪些前驱状态可以到达当前状态。枚举的覆盖性保证不会遗漏最优解，剪枝策略则有助于提升性能。
对一些题目，转移可以是多维的，例如同时考虑行和列、或不同物品的组合。转移边界的设计直接影响时间复杂度。
3.4 选择实现方式与优化方向
本质上，DP 的实现可分为两大流派：自顶向下（带记忆的递归）与自底向上（迭代填表）。不同题型与约束下，各有优势。
在很多现实问题中，空间复杂度可进一步优化，通过滚动数组、按需保留必要行/列等技术达到常数级或线性级空间。
3.5 题解模板与常见坑点
一个稳定的 DP 题解通常包含：状态定义、边界、转移、实现方式、复杂度分析。新手容易在状态定义上犯错，如过度划分导致状态爆炸，或忘记处理边界情况。模板化思维有助于避免这类问题。
4. 示例案例与代码模板
4.1 案例：最小路径和（含自顶向下与自底向上实现）
案例背景：给定一个矩阵 grid，其中每个单元格的值表示步入该格的代价，起点在左上，终点在右下，只能向右或向下移动，要求的最小总代价。通过 DP，我们把问题抽象成一个状态表，逐步求解出从起点到每个位置的最小代价。这是一个典型的二维 DP 问题，适合作为初学者的入门题。
以下代码展示了两种实现思路，均利用了状态转移的最优性，并通过边界处理确保正确性。
# 自顶向下（带记忆化）实现
def min_path_sum_topdown(grid):m, n = len(grid), len(grid[0])memo = [[-1] * n for _ in range(m)]def dfs(i, j):if i == m - 1 and j == n - 1:return grid[i][j]if memo[i][j] != -1:return memo[i][j]best = float('inf')if i + 1 < m:best = min(best, dfs(i + 1, j))if j + 1 < n:best = min(best, dfs(i, j + 1))memo[i][j] = grid[i][j] + bestreturn memo[i][j]return dfs(0, 0)# 自底向上实现
def min_path_sum_bottomup(grid):m, n = len(grid), len(grid[0])dp = [[0] * n for _ in range(m)]dp[0][0] = grid[0][0]for i in range(1, m):dp[i][0] = dp[i-1][0] + grid[i][0]for j in range(1, n):dp[0][j] = dp[0][j-1] + grid[0][j]for i in range(1, m):for j in range(1, n):dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]return dp[m-1][n-1]4.2 DP 模板对比与进阶优化
在很多场景下，DP 模板可以进一步优化为<滚动数组，将二维表转化为一行或两行的存储，显著降低空间消耗，尤其在大规模数据下更为明显。实现要点是确保在滚动的过程中，仍然能够正确地获取前驱状态的值。
下面给出一个简化的只用一行的一维滚动实现思路，用于最小路径和的近似场景（前提是某些方程可降维）。
# 一维滚动数组（简化示例，适用于某些等价转移）
def min_path_sum_rolling(grid):m, n = len(grid), len(grid[0])dp = [0] * ndp[0] = grid[0][0]for j in range(1, n):dp[j] = dp[j-1] + grid[0][j]for i in range(1, m):dp[0] += grid[i][0]for j in range(1, n):dp[j] = min(dp[j-1], dp[j]) + grid[i][j]return dp[n-1]通过上述模板与案例，我们完成了从概念到 DP 题解的完整步骤，同时也展示了不同实现策略的实际应用。
