题目的描述给定一个n×nn\times nn×n的方格矩阵矩阵内部分单元格填写正整数剩余单元格数值为 0。起点为矩阵左上角顶点A终点为矩阵右下角顶点B。行走规则每一步仅能向右走一格或向下走一格沿方格边线从顶点移动途经方格可拾取方格内数值方格内数值一旦被拾取第二次经过该方格时数值变为 0无法重复累加。现要求从A到B连续走两条合法路径求两条路径拾取数字总和的最大值。数据范围n≤10n≤10n≤10题目的分析很多初学算法的同学直观思考先跑一次 DP 求出 A→B 单条最优路径把路径上所有格子数值清零再第二次跑 DP 求剩余格子最优路径两次结果相加当作答案。这个思路不成立漏洞非常明显1. 贪心地确定第一条路径不能保证整体最优第一次 DP 求出的只是原矩阵中价值最大的单条路径但本题要求优化的是两条路径的总收益。单条路径取得的数值最大并不意味着以它作为第一条路径后两条路径的总收益也最大。它可能提前取走多个高价值格子使第二条路径能够取得的数值大幅减少反而选择一条单独收益稍低的路径可能为另一条路径保留更多高价值格子从而得到更大的总收益。因此“先求第一条最优路径再求第二条最优路径”本质上是一种贪心策略而这个贪心选择不具备正确性保证。两条路径需要作为一个整体同时优化。2. 单路径 DP 的状态不足以描述两条路径之间的影响第二条路径能够取得哪些数值取决于第一条路径具体经过了哪些格子。然而普通的单路径 DP 状态通常只记录到达某个位置时能够取得的最大值并没有记录这条路径占用了哪些格子。即使第一次 DP 得到了单条最优路径并将其清零第二次 DP 求出的也只是这条已固定路径下的最优补充路径无法与其他第一条路径对应的组合进行比较。所以我们该怎么做这道题呢我们可以在dp[i,j]再加两维即dp[i1,j1,i2,j2]。这样dp就可以定义为从走(1,1)(1,1)分别走到(i1,j1)(i2,j2)的所有路径中取得的最大值。其实我们还可以继续优化我们知道一条路径走到一个点这个点就要清零即两条路径走到相同的点这个点的值只能加一次。那么我们可以设kki1j1i2j2ki1j1i2j2ki1j1i2j2这样当两次路径走到的点横纵坐标之和相等时此时才有可能走到相同的点反之不一定。然后我们可以压缩dp的维度即dp[k,i1,i2]后续计算j1j2时我们可以通过公式j1k−i1,j2k−i2j1k-i1,j2k-i2j1k−i1,j2k−i2计算而且每次状态计算还能保证j1,j2j1,j2j1,j2唯一所以与原四维dp的状态定义等价。现在我们采用闫氏DP分析法来分析这道题首先状态表示从上方分析得dp[k,i1,i2]集合从走(1,1)(1,1)分别走到(i1,j1)(i2,j2)的所有路径。属性Max即dp[k,i1,i2]为从走(1,1)(1,1)分别走到(i1,j1)(i2,j2)的所有路径中取得的最大值。ki1j1i2j2ki1j1i2j2ki1j1i2j2然后状态计算开始划分集合我们以最后一个集合dp[k,i1,i2]来划分它可以划分成从(i1−1,j1)(i2−1,j2),(i1,j1−1)(i2,j2−1),(i1−1,j1)(i2,j2−1),(i1,j1−1)(i2−1,j2)(i1-1,j1)(i2-1,j2),(i1,j1-1)(i2,j2-1),(i1-1,j1)(i2,j2-1),(i1,j1-1)(i2-1,j2)(i1−1,j1)(i2−1,j2),(i1,j1−1)(i2,j2−1),(i1−1,j1)(i2,j2−1),(i1,j1−1)(i2−1,j2)这四个方向到(i1,j1)(i2,j2)(i1,j1)(i2,j2)(i1,j1)(i2,j2)点(i1,j1)(i1,j1)(i1,j1)的值为w1w1w1点(i2,j2)(i2,j2)(i2,j2)的值为w2w2w2所以我们可以把这个集合划分为dp[k-1,i1-1,i2]w1w2dp[k-1,i1,i2-1]w1w2dp[k-1,i1,i2]w1w2dp[k-1,i1-1,i2-1]w1w2当i1i2和j1j2i1i2和j1j2i1i2和j1j2同时成立时此时w1w2w1w2w1w2我们只能让dp加一次w1然后取它们四个方向到该集合的最大值即可即inttw[i1][j1];if(i1!i2)tw[i2][j2];intxdp[k][i1][i2];// 状态转移方程xmax(x,dp[k-1][i1-1][i2-1]t);xmax(x,dp[k-1][i1-1][i2]t);xmax(x,dp[k-1][i1][i2-1]t);xmax(x,dp[k-1][i1][i2]t);闫氏DP分析图题目的代码题目链接https://www.acwing.com/problem/content/1029/#includeiostream#includealgorithmusingnamespacestd;constintN15;intn;intw[N][N];intf[N*2][N][N];intmain(){scanf(%d,n);inta,b,c;while(cinabc,a||b||c)w[a][b]c;for(intk2;knn;k)for(inti11;i1n;i1)for(inti21;i2n;i2){intj1k-i1,j2k-i2;if(j11j1nj21j2n){inttw[i1][j1];if(i1!i2)tw[i2][j2];intxf[k][i1][i2];xmax(x,f[k-1][i1-1][i2-1]t);xmax(x,f[k-1][i1-1][i2]t);xmax(x,f[k-1][i1][i2-1]t);xmax(x,f[k-1][i1][i2]t);}}printf(%d\n,f[nn][n][n]);return0;}**时间复杂度**只需遍历dp数组所以复杂度为O(n3)\boldsymbol{O(n^3)}O(n3)**空间复杂度**只需开2*n*n*n个数组所以复杂度为O(n3)\boldsymbol{O(n^3)}O(n3)