1. 方格取数问题从NOIP竞赛到动态规划入门第一次接触方格取数问题是在准备NOIP比赛的时候当时看到这个题目就感觉特别有意思。想象一下你站在一个n×n的棋盘左上角每次只能向右或向下走目标是到达右下角。棋盘每个格子里都有一个数字走过这个格子就能拿到对应的分数。现在问题来了如果让你走两遍这个棋盘怎样走才能拿到最多的分数呢这个问题看似简单但仔细想想会发现很多坑。比如如果两遍都走同样的路径那么第二次走的时候分数已经被拿走了就不能重复计算。这就是典型的双线程动态规划问题也是NOIP/NOI竞赛中经常出现的经典题型。我在初学动态规划时老师总是强调要找到最优子结构和重叠子问题。方格取数问题完美体现了这两个特性。最优子结构体现在到达某个格子的最大分数取决于之前格子的最优选择重叠子问题则体现在两条路径可能会经过相同的中间状态。2. 从单线程到双线程DP思维的跃迁2.1 单路径问题的基本解法先回忆下单路径问题的解法。假设只要走一遍棋盘我们可以定义一个二维DP数组dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]这个状态转移方程非常直观到达(i,j)点的最大分数要么来自上方要么来自左方取较大值加上当前格子的分数。我第一次写这个代码时犯了个典型错误——忘记处理边界条件。当i1或j1时i-1或j-1会越界。后来学会了要么把数组开大一圈要么单独处理边界情况。2.2 双路径问题的思维转换当问题变成两条路径时情况就复杂多了。最直观的想法是先走第一条路径拿走分数后修改棋盘再走第二条路径。但这样得到的往往不是最优解因为第一条路径的选择会影响第二条路径的可能性。正确的做法是同时考虑两条路径。这时候状态定义就需要升级为四维dp[i][j][k][l] # 第一条路径到(i,j)第二条路径到(k,l)时的最大得分这个思维跳跃很关键——从单独考虑两个过程转变为同时考虑两个过程的联合状态。这也是双线程DP的核心思想。3. 四维DP的详细拆解3.1 状态定义的艺术定义dp[i][j][k][l]表示第一条路径从(1,1)走到(i,j)第二条路径从(1,1)走到(k,l)两条路径获得的数字总和最大值这里有个重要观察因为每次只能向右或向下走所以两条路径的步数总是相同的。也就是说ij kl。这个性质可以帮助我们优化空间复杂度后面会讲到。3.2 状态转移方程的推导状态转移需要考虑四种情况第一条路径从上方来第二条路径从上方来第一条路径从上方来第二条路径从左方来第一条路径从左方来第二条路径从上方来第一条路径从左方来第二条路径从左方来特别要注意的是当(i,j)和(k,l)是同一个格子时分数只能加一次。用代码表示就是if ik and jl: dp[i][j][k][l] max(四种情况) a[i][j] else: dp[i][j][k][l] max(四种情况) a[i][j] a[k][l]3.3 边界条件的处理边界处理总是容易出错的地方。对于i,j,k,l1的情况当i1时不能从i-1来只能从j-1来同理适用于其他维度在实际编程中我习惯把dp数组的0行和0列都初始化为0然后从(1,1)开始计算。这样就不需要特殊处理边界了。4. 优化技巧从四维到三维4.1 利用步数相同的性质注意到ij kl我们可以设s ij kl这样就把状态降为三维dp[s][i][k] # s表示步数i和k分别表示两条路径的行坐标列坐标可以通过j s-i和l s-k计算得到。这个优化让空间复杂度从O(n^4)降到了O(n^3)对于n10的情况可能差别不大但当n增大时优势就很明显了。4.2 滚动数组技巧进一步优化空间可以观察到每个状态只依赖于s-1步的状态。所以只需要保存当前步和上一步的两个二维数组即可空间复杂度降到O(n^2)。不过在实际比赛中除非n特别大否则用三维数组通常就足够了。优化到滚动数组虽然节省空间但代码可读性会降低容易出错。5. 代码实现与调试技巧5.1 基础四维DP实现以C为例基础实现如下int dp[N][N][N][N]; int a[N][N]; // 输入省略... for(int i1; in; i) for(int j1; jn; j) for(int k1; kn; k) for(int l1; ln; l) { int max_val max(max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]), max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1])); if(ik jl) dp[i][j][k][l] max_val a[i][j]; else dp[i][j][k][l] max_val a[i][j] a[k][l]; } cout dp[n][n][n][n];5.2 常见错误与调试在实现过程中我踩过几个坑数组越界忘记处理i,j,k,l1的情况分数重复计算当(i,j)(k,l)时忘记只加一次分数初始化问题dp[1][1][1][1]应该初始化为a[1][1]的2倍还是1倍实际上是1倍因为是一个格子调试时可以打印中间状态。对于n较小的情况比如n3手工计算几个关键点的dp值与程序输出对比。6. 问题变种与扩展思考6.1 k条路径的情况如果题目变成走k条路径呢理论上可以用2k维DP但显然不现实。这时候可能需要考虑网络流等其他算法。这也说明了DP不是万能的要因题制宜。6.2 带障碍物的棋盘如果棋盘中某些格子不能通过状态转移时需要额外判断。这时候DP的定义可以保持不变只是在计算时跳过障碍物格子即可。6.3 其他双线程DP问题类似的思路可以应用于其他双线程问题比如两个人在迷宫中同时移动同时处理两个序列的问题资源分配问题中的两种并行决策7. 实际比赛中的应用策略在NOIP等比赛中遇到这类题目我的经验是先想清楚状态定义在白纸上写出状态转移方程考虑边界条件和初始状态先写基础版本确保正确性如果有时间再考虑优化空间用小的测试用例验证记得有一次比赛我花了太多时间想优化结果基础版本都没写完。后来学乖了先保证能拿基础分再说。8. 从算法到思维的提升双线程DP不仅是一个算法技巧更是一种思维方式。它教会我们如何将复杂问题分解如何设计多维状态来描述问题如何在时空复杂度之间权衡这些思维方法在解决其他复杂问题时也同样适用。比如在系统设计中经常需要考虑多个并发的流程这时候双线程DP的思维模式就能派上用场。