洛谷 P1004 总结
题目：洛谷 P1004
链接：洛谷，vjudge
题意
-
有一个 \(n \times n\) 的矩阵，有些方格放入了一个·正整数，其他方格为 \(0\)，现在要从 \(A\) 走到 \(B\) 走两次（只能往下或右走），走到一个非 \(0\) 格子就会把这个数取走，格子里的数变为 \(0\)。问最大取走数字之和。
-
\(1 \le n \le 9\)。
思路
暴力
首先我们可以进行两次搜索，在统计答案。
优化
我们可以进行优化，将第二重搜索改为 \(DP\)。
\(n^4\) DP
-
接下来我们要思考如何去掉第一种搜索。可以定义状态：\(dp_{i,j,k,l}\) 表示第一次走走到 \((i,j)\)，第二次走到 \((k,l)\) 能得到的最大数字之和，\(dp_{i,j，k,l} = \max\{dp_{i',j',k',l'}\} + a_{i,j} + a_{k,l}\)，当然如果 \((i,j) = (k,l)\)，只能加一次，因为每个数只能去走一次。
-
初始：\(dp_{1,1,1,1} = a_{1,1}\)，目标：\(dp_{n,n,n,n}\)。
\(n^3\) DP
- 可以发现 \(n^4\) DP 的状态两次走的步数是相同，所以只要知道了其中三个，另一个就求出来了，所以最后一位可以优化掉。