动态规划入门：从数字三角形到网格路径问题的核心思想与C++实现

1. 项目概述从数字三角形到经典模型动态规划DP是算法学习路上的一道分水岭也是面试中区分候选人水平的关键。很多朋友一听到“状态转移方程”就头疼感觉像在解天书。其实动态规划的核心思想非常朴素把大问题拆成小问题记住已经解决过的小问题的答案避免重复计算。今天我们不谈那些空泛的理论直接从一个最经典、最直观的模型入手——数字三角形模型。这个模型是理解二维坐标系下动态规划的绝佳起点它像一把钥匙能帮你打开“摘花生”、“方格取数”、“传纸条”等一系列经典问题的大门。我刚开始学DP时也是从数字三角形“爬”过来的。这个模型之所以重要是因为它完美地展示了动态规划的两个核心要素状态表示和状态计算。状态表示就是“我们用什么来描述当前局面”在数字三角形里通常就是用二维坐标(i, j)来表示“走到第i行第j列这个位置”。状态计算就是“当前局面的答案能从哪些更小的、已经解决的局面的答案推导出来”在数字三角形里就是“从上方的两个位置走过来选一条最优路径”。掌握了这个模型的精髓你会发现后面很多看似复杂的题目比如在网格里摘花生、计算最低通行费、甚至两个人同时走网格传纸条其内核都是数字三角形模型的变种或扩展。它们的状态定义和转移逻辑有着深刻的血缘关系。本篇内容我将带你彻底吃透这个模型不仅分析其原理还会用C手把手实现五个经典例题数字三角形、摘花生、最低通行费用、方格取数、传纸条并分享我在刷题和教学中总结出的、那些普通题解里不会告诉你的“避坑指南”和“优化心法”。2. 数字三角形模型的核心思想与状态设计2.1 模型抽象把问题装进网格数字三角形模型解决的问题通常发生在一个二维的网格或三角形网格中。我们有一个明确的起点通常是左上角或顶点一个明确的终点通常是右下角或底边某个位置以及一系列明确的移动规则比如只能向下、向右走。我们的目标是从起点到终点按照规则移动使得路径上经过的“数字”可以理解为价值、成本、分数等之和满足某种最优条件最大或最小。为什么叫“数字三角形”最初的原型问题就是在一个三角形的数字阵列中从顶部走到底部求路径最大和。因为它的结构像三角形所以得名。但这个模型的思维方式完全可以平移到矩形的网格中。这个模型的核心在于我们将整个行走过程分解成了一个个按顺序抵达的“状态”。每个状态由你在网格中的位置(i, j)唯一确定。我们定义f[i][j]为从起点走到位置(i, j)时所能获得的某种最优值如最大和、最小成本。这个f[i][j]就是我们所说的“状态”。2.2 状态转移当前答案从何而来定义了状态接下来最关键的一步就是建立状态之间的联系也就是状态转移方程。这是动态规划的灵魂。在基础的数字三角形或只能向下、向右走的网格中到达(i, j)这个位置只能从它的上方(i-1, j)或者左方(i, j-1)走过来假设起点在左上终点在右下。不可能从其他地方凭空跳过来。这就是所谓的“拓扑序”保证了我们在计算f[i][j]时f[i-1][j]和f[i][j-1]一定已经被计算出来了。那么f[i][j]的值就应该等于从起点到(i-1, j)的最优值加上(i, j)位置本身的值w[i][j]或者从起点到(i, j-1)的最优值加上w[i][j]。我们要根据问题要求选择“最大”或“最小”。 因此状态转移方程通常写作f[i][j] max(f[i-1][j], f[i][j-1]) w[i][j]求最大和 或f[i][j] min(f[i-1][j], f[i][j-1]) w[i][j]求最小成本这就是最朴素的状态转移。对于原始的数字三角形问题行走方向为向下或向右下方程则变为f[i][j] max(f[i-1][j-1], f[i-1][j]) w[i][j]注意这里隐藏了一个非常重要的细节——边界处理。对于第一行i0和第一列j0的位置它们没有“上方”或“左方”的状态。因此我们需要在初始化或状态转移时进行特殊处理。通常的做法是将f数组初始化为一个不可能的值求最大值时初始化为负无穷求最小值时初始化为正无穷然后将起点f[0][0]初始化为w[0][0]。在状态转移时需要判断(i-1, j)和(i, j-1)是否合法即坐标是否在网格内再参与计算。另一种更简洁的做法是将f数组多开一圈行和列都从1开始计数并将这一圈初始化为“哨兵”值如求最大值时第0行和第0列初始化为负无穷这样在计算f[1][1]及以后时就可以统一使用转移方程无需额外判断。我强烈推荐第二种“多开一圈”的做法它能极大简化代码逻辑减少出错可能。2.3 模型的价值为什么它是基础你可能会问这个模型看起来这么简单有什么用它的巨大价值在于其可扩展性。今天分析的五个例题就是在这个核心模型上通过增加不同的“约束条件”和“问题维度”演化而来的。数字三角形模型的原型行走方向受限左下/右下。摘花生模型在矩形网格上的直接应用行走方向受限向下/向右求最大和。最低通行费用同样是矩形网格行走方向受限向下/向右但求的是最小成本。这提醒我们状态转移方程中的max和min需要根据问题灵活选择。方格取数引入了“两个人同时走”这一新维度。状态从描述一个人的位置(i, j)升级为描述两个人的位置(i1, j1, i2, j2)。这是模型从二维向高维的拓展但其核心的“状态表示状态转移”思想一脉相承。传纸条可以看作是“方格取数”问题的一个变体通常增加了“每个数字只能被取一次”的约束即使两个人经过同一个格子。这要求我们在状态转移时对两人走到同一格的情况进行特殊判断和处理。通过这五个由浅入深的例题你能清晰地看到动态规划模型是如何像搭积木一样从简单到复杂构建起来的。理解了这个过程你再遇到新的网格类DP问题就不会无从下手而是能主动去分析它的状态应该如何定义在基础模型上增加了哪些限制状态转移需要如何调整3. 核心例题深度剖析与C实现理论讲得再多不如一行代码来得实在。接下来我们逐一拆解这五个经典例题我会给出清晰的思路分析和可以直接“抄作业”的C代码实现。代码中会包含详细的注释并指出一些容易踩坑的地方。3.1 例题一数字三角形原型问题描述给定一个层数为n的数字三角形从顶部出发在每一结点可以选择移动至其左下方的结点或右下方的结点一直走到底层要求找出一条路径使路径上的数字之和最大。思路分析 这是最标准的模型。状态f[i][j]表示从顶点走到第i行第j列假设行和列都从1开始的所有路径中数字和的最大值。 由于只能从左上(i-1, j-1)或正上(i-1, j)走过来所以状态转移方程为f[i][j] max(f[i-1][j-1], f[i-1][j]) w[i][j]初始化f[1][1] w[1][1]顶点。 最终答案max(f[n][j])其中j从1到n底层所有位置中的最大值。C代码实现#include iostream #include algorithm using namespace std; const int N 510, INF 1e9; int w[N][N]; // 存储数字三角形 int f[N][N]; // dp状态数组 int main() { int n; cin n; // 读入数据注意三角形不是矩形第i行有i个数 for (int i 1; i n; i) for (int j 1; j i; j) cin w[i][j]; // 初始化为了处理边界我们将f数组全部初始化为负无穷 // 这样那些“不可能”的状态如三角形外的位置就不会被选中 for (int i 0; i n; i) for (int j 0; j i 1; j) // 注意这里j的范围要到i1因为右上角也可能被访问 f[i][j] -INF; // 基础状态起点 f[1][1] w[1][1]; // 状态计算从第二行开始 for (int i 2; i n; i) for (int j 1; j i; j) f[i][j] max(f[i-1][j-1], f[i-1][j]) w[i][j]; // 遍历最后一行找出最大值 int res -INF; for (int j 1; j n; j) res max(res, f[n][j]); cout res endl; return 0; }实操心得初始化成负无穷-INF是关键一步。如果不这样做对于边界上的点如最左边的点只有f[i-1][j]是合法的f[i-1][j-1]是非法索引在max比较时未初始化的f[i-1][j-1]可能是一个随机的大正数导致错误地选中这条不存在的路径。将非法状态初始化为一个“极差”的值就能保证它们不会被选为最优解。3.2 例题二摘花生问题描述一个R行C列的网格每个格子有若干花生。从左上角(1,1)出发每次只能向下或向右走到达右下角(R,C)。求能摘到的花生最大总数。思路分析 这是数字三角形模型在矩形网格上的直接应用。状态f[i][j]表示从(1,1)走到(i,j)能摘到的花生最大数量。 状态转移f[i][j] max(f[i-1][j], f[i][j-1]) w[i][j]。 初始化f[1][1] w[1][1]。或者更通用的将f[0][*]和f[*][0]初始化为0因为从网格外走进来是没有花生的然后从(1,1)开始正常转移。 最终答案f[R][C]。C代码实现#include iostream #include algorithm using namespace std; const int N 110; int w[N][N], f[N][N]; int main() { int T; cin T; while (T--) { int R, C; cin R C; for (int i 1; i R; i) for (int j 1; j C; j) cin w[i][j]; // 初始化我们可以选择将第0行和第0列初始化为0 // 这样f[1][1] max(f[0][1], f[1][0]) w[1][1] 0 w[1][1]结果正确 // 代码中可以省略显式初始化因为全局数组默认值为0 // for (int i 0; i R; i) f[i][0] 0; // for (int j 0; j C; j) f[0][j] 0; for (int i 1; i R; i) for (int j 1; j C; j) f[i][j] max(f[i-1][j], f[i][j-1]) w[i][j]; cout f[R][C] endl; } return 0; }避坑技巧对于这种“多组测试数据”的题目一定要记得在每组数据开始前清空或重新初始化f数组。如果使用全局数组由于上一组数据的结果还残留着会导致下一组计算错误。简单的做法是像上面一样在while(T--)循环内直接定义f数组C局部变量默认值不确定但这里我们会在计算中覆盖或者使用memset在循环开始前清空。我更喜欢在循环内定义逻辑更清晰。3.3 例题三最低通行费用问题描述一个N x N的网格每个格子有一个正整数表示经过该格子的费用。从左上角(1,1)出发走到右下角(N,N)每步只能向下或向右走。求所需的最低通行费用。思路分析 这道题几乎是“摘花生”的镜像问题只不过把求“最大值”换成了求“最小值”。状态定义不变f[i][j]表示从(1,1)走到(i,j)所需的最低费用。 状态转移f[i][j] min(f[i-1][j], f[i][j-1]) w[i][j]。关键区别在于初始化因为求最小值我们需要将f数组初始化为一个很大的数如0x3f3f3f3f这个数在ACM竞赛中常被用作“无穷大”的近似值因为它满足0x3f3f3f3f 0x3f3f3f3f不会溢出int且足够大。同时起点(1,1)的费用就是w[1][1]所以f[1][1]应初始化为w[1][1]。但为了统一转移公式我们通常将f[0][1]和f[1][0]初始化为0这样f[1][1] min(f[0][1], f[1][0]) w[1][1] 0 w[1][1]。C代码实现#include iostream #include cstring #include algorithm using namespace std; const int N 110, INF 0x3f3f3f3f; int w[N][N], f[N][N]; int main() { int n; cin n; for (int i 1; i n; i) for (int j 1; j n; j) cin w[i][j]; // 初始化因为求最小值先全部置为无穷大 memset(f, 0x3f, sizeof f); // 设置边界条件从虚拟的“网格外”走进(1,1)点费用为0 f[0][1] f[1][0] 0; // 也可以这样初始化直接设置f[1][1]但需要调整循环起点 // f[1][1] w[1][1]; for (int i 1; i n; i) for (int j 1; j n; j) // 如果采用设置f[1][1]的方式这里i和j要从1开始并且要判断i1j1的情况 // 采用设置f[0][1]和f[1][0]的方式代码更统一 f[i][j] min(f[i-1][j], f[i][j-1]) w[i][j]; cout f[n][n] endl; return 0; }注意事项0x3f3f3f3f是一个约等于10^9的数对于大多数题目中的费用累加是足够大的。使用memset按字节赋值时0x3f会填充到每个字节因此int变量的四个字节都会变成0x3f最终值就是0x3f3f3f3f。这是竞赛编程中的一个常用技巧。3.4 例题四方格取数问题描述设有N x N的方格图某些方格中放有正整数。某人从左上角的A(1,1)点出发可以向下或向右走直到到达右下角的B(N,N)点。在走过的路上他可以取走方格中的数取走后方格中将变为数字0。此人从A点到B点共走两次求能取得的数字之和最大是多少。思路分析 这是数字三角形模型的第一次重大升级从一个人走一次变成同一个人走两次。一个最直接的思路是先走第一次取走数然后走第二次。但问题在于第一次走的选择会影响第二次走时网格的状态有些格子变空了。这使得问题变得复杂难以分步处理。一个经典的技巧是将两次行走视为同时进行。我们想象有两个人A和B同时从(1,1)出发走向(N,N)每个人都只能向下或向右走。这样我们需要一个状态来同时描述两个人的位置。定义状态f[k][i1][i2]k表示两个人走过的步数之和。因为每一步每个人只能向下或向右走一格所以从起点开始当两人共走了k步时A的坐标是(i1, k-i1)B的坐标是(i2, k-i2)。这里i1和i2分别是两人所在的行号。通过k和行号可以唯一确定列号。这样就把四维状态(i1, j1, i2, j2)优化到了三维(k, i1, i2)这是一个非常重要的优化。f[k][i1][i2]表示两个人分别走到(i1, k-i1)和(i2, k-i2)时已经取到的数字之和的最大值。状态转移每个人上一步都有两种可能从上来或从左来所以组合起来共有2x24种转移方式A从上B从上f[k-1][i1-1][i2-1]A从上B从左f[k-1][i1-1][i2]A从左B从上f[k-1][i1][i2-1]A从左B从左f[k-1][i1][i2]对于当前格子(i1, j1)和(i2, j2)如果两个位置不同i1 ! i2意味着j1 ! j2因为k相同那么可以取走两个格子的数。如果两个位置相同即两个人走到了同一个格子那么这个格子的数只能被取走一次。所以状态转移方程为f[k][i1][i2] max(四种转移来源) t其中t是本次走到的两个格子所能获得的数字之和。如果i1 i2两人同格则t w[i1][k-i1]否则t w[i1][k-i1] w[i2][k-i2]。初始化f[2][1][1] w[1][1]起点步数k2因为从(1,1)到(1,1)走了0步这里需要仔细定义。通常我们定义k为横纵坐标之和这样起点(1,1)的k2。那么f[2][1][1]就是初始状态值为起点的数字。 最终答案f[2*N][N][N]终点(N,N)的横纵坐标之和为2N。C代码实现#include iostream #include algorithm using namespace std; const int N 15; int w[N][N]; int f[N * 2][N][N]; // f[k][i1][i2] int main() { int n; cin n; int a, b, c; while (cin a b c, a || b || c) w[a][b] c; // k从2开始因为起点(1,1)的ij2 for (int k 2; k n n; k) { for (int i1 1; i1 n; i1) { for (int i2 1; i2 n; i2) { int j1 k - i1, j2 k - i2; // 判断坐标是否合法 if (j1 1 j1 n j2 1 j2 n) { int t w[i1][j1]; if (i1 ! i2) t w[i2][j2]; // 不是同一个格子加两份 int x f[k][i1][i2]; // 四种状态转移 x max(x, f[k-1][i1-1][i2-1] t); // 下下 x max(x, f[k-1][i1-1][i2] t); // 下右 x max(x, f[k-1][i1][i2-1] t); // 右下 x max(x, f[k-1][i1][i2] t); // 右右 } } } } cout f[n n][n][n] endl; return 0; }深度解析为什么状态定义成f[k][i1][i2]是可行的关键在于在只能向下和向右走的规则下当总步数k即横纵坐标之和固定时知道了行号i列号j就唯一确定了j k - i。这利用了行走规则带来的约束将四维状态压缩到了三维大大降低了空间和时间复杂度从O(N^4)降到O(N^3)。这是解决此类“双路径”问题的核心技巧务必理解透彻。3.5 例题五传纸条问题描述一个M行N列的矩阵每个格子有一个正整数。有两条传纸条的路径都是从左上角(1,1)到右下角(M,N)且路径除了起点和终点外不能有交点。求两条路径上数字之和的最大值。思路分析 这道题与“方格取数”非常相似都是两个人从左上到右下。区别在于约束条件“不能有交点”除了起点和终点。这意味着在行走过程中任何时刻两个人都不能走到同一个格子。如果我们直接套用“方格取数”的解法在状态转移时当i1 i2即两人同格时我们只加一次格子的值。但这并不能物理上避免“经过”同一个格子只是避免了“重复计算”该格子的值。对于“传纸条”问题我们需要在状态转移时就禁止两人走到同一个格子的情况起点和终点除外。因此状态定义和转移方程与“方格取数”几乎完全一致唯一的区别是在计算t本次获得的数字时如果i1 i2即两人同格我们直接跳过这种状态不进行更新。或者在循环内部判断如果i1 i2 k ! 2 k ! mn即不是起点也不是终点则continue。这里有一个重要的等价转换可以证明“找两条不相交路径”的最大和等价于“找两条路径允许路径相交但相交点的值只计算一次”的最大和。因为如果两条最优路径有交点我们可以通过调整其中一条路径在交点附近的行进顺序得到两条新的、和不变且不相交的路径“绕路”思想。因此很多情况下“传纸条”的代码可以和“方格取数”完全一样。但为了严格满足题意“不能有交点”我们可以在代码中加上同格判断。C代码实现严格不相交版本#include iostream #include algorithm using namespace std; const int M 55, N 55; int w[M][N]; int f[M N][M][M]; // f[k][i1][i2] int main() { int m, n; cin m n; for (int i 1; i m; i) for (int j 1; j n; j) cin w[i][j]; for (int k 2; k m n; k) { for (int i1 1; i1 m; i1) { for (int i2 1; i2 m; i2) { int j1 k - i1, j2 k - i2; if (j1 1 j1 n j2 1 j2 n) { // 关键判断如果走到同一格且不是起点或终点则跳过 if (i1 i2 k ! 2 k ! m n) continue; int t w[i1][j1]; if (i1 ! i2) t w[i2][j2]; int x f[k][i1][i2]; x max(x, f[k-1][i1-1][i2-1] t); x max(x, f[k-1][i1-1][i2] t); x max(x, f[k-1][i1][i2-1] t); x max(x, f[k-1][i1][i2] t); } } } } cout f[m n][m][m] endl; return 0; }经验之谈在实际做题和竞赛中对于“传纸条”这类问题通常直接使用“方格取数”的代码即允许同格但值只加一次也能通过评测。这是因为题目数据通常满足“最优解路径可以做到不相交”的性质或者评测系统没有严格检查路径是否相交只检查和值。但从严谨理解和应对不同出题人意图的角度掌握严格不相交的写法更有保障。理解两者之间的等价关系能帮助你更灵活地应对问题变种。4. 动态规划优化技巧与常见问题排查通过上面五个例题我们已经掌握了数字三角形模型的基本框架和扩展方法。但在实际编码和解题中还会遇到一些性能问题和细节坑点。这部分分享一些优化技巧和排查问题的经验。4.1 空间优化滚动数组在“摘花生”、“最低通行费”这类简单的二维DP中状态转移方程只依赖于上一行i-1和当前行的左边j-1。这意味着我们并不需要保存整个N x N的f数组。我们可以只用两行数组甚至一行来滚动更新。以“摘花生”为例状态转移为f[i][j] max(f[i-1][j], f[i][j-1]) w[i][j]。当我们计算第i行时只需要第i-1行的数据。对于第i行内部的jf[i][j-1]是刚刚计算过的本行左边的值。因此我们可以定义一个f[2][N]的数组用i % 2来滚动。更进一步的可以只用一个一维数组f[N]int f[N]; for (int i 1; i R; i) { for (int j 1; j C; j) { // 在计算f[j]时它原来的值代表的是上一行的f[i-1][j] // f[j-1]代表的是本行已经计算过的f[i][j-1] f[j] max(f[j], f[j-1]) w[i][j]; } }解释在进入第i行的内层循环前f[j]中存储的是上一行i-1的结果即f[i-1][j]。在内层循环中当我们按j从1到C的顺序计算时f[j-1]已经被更新为本行i的结果即f[i][j-1]。所以max(f[j], f[j-1])正好对应了max(f[i-1][j], f[i][j-1])。计算完成后f[j]被更新为f[i][j]。这样我们用一个一维数组就完成了二维DP的计算空间复杂度从O(N^2)降到了O(N)。注意事项使用一维滚动数组时循环顺序至关重要。必须是i从1到R行j从1到C列的顺序。如果j从C到1逆序循环那么f[j-1]在计算f[j]时还是上一行的值逻辑就错了。对于“最低通行费”这种求最小值的问题优化方法完全一样。4.2 路径记录与方案输出有时题目不仅要求最优值还要求输出具体路径。这时我们需要在状态转移时额外记录每个状态是从哪个前驱状态转移过来的。以“摘花生”为例我们可以用一个pre[i][j]数组记录走到(i,j)时上一步是来自上方(i-1,j)还是左方(i,j-1)。通常用数字表示比如0表示来自上方1表示来自左方。 在状态转移时if (f[i-1][j] f[i][j-1]) { f[i][j] f[i-1][j] w[i][j]; pre[i][j] 0; // 来自上方 } else { f[i][j] f[i][j-1] w[i][j]; pre[i][j] 1; // 来自左方 }输出路径时从终点(R,C)开始根据pre数组记录的方向不断回溯到起点(1,1)再将路径逆序输出即可。vectorpairint, int path; int i R, j C; while (i 1 || j 1) { path.push_back({i, j}); if (pre[i][j] 0) i--; else j--; } path.push_back({1, 1}); reverse(path.begin(), path.end()); for (auto p : path) cout p.first p.second endl;4.3 常见错误与调试技巧数组越界这是DP问题中最常见的错误。尤其是在处理边界第一行、第一列时。强烈建议使用“多开一圈”的初始化方法并将外围格子初始化为一个不会影响状态转移的值求最大初始化为负无穷求最小初始化为正无穷。这能从根本上避免复杂的边界判断。状态转移方程写错仔细审题明确移动规则。是“向下/向右”还是“向下/向右下”是求最大值还是最小值在“方格取数”这类高维DP中要理清所有可能的前驱状态。初始化错误起点状态f[1][1]必须正确初始化。对于求最小值问题其他状态要初始化为一个很大的数确保它们能被正确更新。循环顺序错误在二维DP中通常需要保证在计算f[i][j]时它所依赖的状态如f[i-1][j]和f[i][j-1]都已经计算完毕。所以通常采用i从1到nj从1到m的双重循环顺序。在使用滚动数组优化时内层循环的顺序正序或逆序至关重要。数据类型溢出路径和或费用累加可能超出int范围。如果题目给出的数字较大或网格较大要使用long long来定义状态数组。调试技巧打印中间状态在程序运行时打印出f数组的内容与手动模拟的小样例进行对比。这是最直接的调试方法。从小样例开始不要一上来就用复杂的大数据测试。先设计一个2x2或3x3的网格手动计算出最优值和路径然后用程序跑看结果是否一致。使用断言在关键步骤后加入断言检查数组索引是否合法、状态值是否在合理范围内。5. 从模型到泛化解决更复杂的网格DP问题掌握了数字三角形模型及其经典变种你已经具备了解决一大类网格DP问题的基础。但实际遇到的问题可能更加复杂。这里提供一些思路帮助你将这个模型泛化。5.1 行走规则的扩展基础的模型只允许向下和向右走。但问题可能允许更多方向比如“向下、向右、向右下”数字三角形原型或者“上下左右”四个方向此时通常会有“不能重复走”或“有步数限制”等额外约束。当移动规则变化时状态转移方程中“前驱状态”的来源就会增加。例如如果允许向上走那么状态转移就可能出现环需要更复杂的处理方法如最短路算法、SPFA等。在竞赛中网格DP通常保证移动具有“拓扑序”即不会走回头路形成环。5.2 状态属性的增加我们之前的状态f[i][j]只记录了“走到(i,j)的最优值”。但问题可能附加其他条件比如有拾取限制“最多只能取K个物品”。这时状态需要增加一维变成f[i][j][k]表示走到(i,j)且已经取了k个物品时的最优值。有状态依赖“某些格子只有满足特定条件如拥有钥匙才能进入”。这时状态也需要增加一维来表示是否拥有钥匙。求方案数如果问题不是求最优值而是求有多少种方式走到终点。那么状态f[i][j]就表示走到(i,j)的方案数。状态转移方程从max/min变为求和f[i][j] f[i-1][j] f[i][j-1]如果只能向下向右。初始化f[1][1] 1。5.3 高维状态的压缩技巧“方格取数”问题展示了通过寻找变量之间的关系k i j来压缩状态维度的方法。这是一种非常重要的优化思想。当状态维度过高导致复杂度无法承受时就要思考状态参数之间是否存在等式或不等式的约束能否用更少的变量来表示同样的信息。5.4 结合其他算法思想动态规划也常与其他算法思想结合。例如预处理先通过一次DFS或BFS计算出每个格子的某些信息如离某个目标的距离作为DP状态的权重或约束条件。二分答案DP验证当问题要求“最大化最小值”或“最小化最大值”时可以二分这个答案然后用DP来验证在当前答案限制下是否存在可行路径。数字三角形模型是动态规划大厦的一块坚实基石。它教给我们的不仅仅是几行状态转移代码更重要的是一种建模思想如何将一个问题分解为阶段和状态如何定义状态表示如何构建状态之间的转移关系以及如何通过优化技巧让算法更高效。当你遇到一个新的网格类问题时不妨先问自己它和数字三角形模型有多像差异在哪里状态需要增加什么维度转移方程需要如何调整多进行这样的思考和实践你解决动态规划问题的能力一定会稳步提升。