题目：洛谷 P1004
题意
-
有一个 \(n \times n\) 的矩阵，有些方格放入了一个·正整数，其他方格为 \(0\)，现在要从 \(A\) 走到 \(B\) 走两次（只能往下或右走），走到一个非 \(0\) 格子就会把这个数取走，格子里的数变为 \(0\)。问最大取走数字之和。
-
\(1 \le n \le 9\)。
思路
暴力
首先我们可以进行两次搜索，在统计答案。
优化
我们可以进行优化，将第二重搜索改为 \(DP\)。
\(n^4\) DP
- 接下来我们要思考如何去掉第一种搜索。可以定义状态：\(dp_{i}{j}{k}{l}\) 表示第一次走走到 \((i,j)\)，