[NOIP2000 提高组] 方格取数 题目描述 设有 N × N N \times N N×N 的方格图 ( N ≤ 9 ) (N \le 9) (N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0 0 0。如下图所示（见样例）: 某人从图的左上角的 A A A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B B B 点。在走过的路上，他可以取

链接：https://www.luogu.org/problem/show?pid=1004 这是一道很经典的多进程动态规划题 一个自然的想法是：贪心地将前面的取过的数全赋成0，然后再取一次，然而并不对（QAQ） 第一次取的显然是最大值，但第二次取的未必是次大值，所以两条非最大的路，也许比一条最大加一条小一点的路更优。 动态规划里的一个重要思想就是，当前的状态无法表示时，可以增添一维来表示

洛谷 P1004 方格取数 1.问题分析2.具体代码3.总结 题目链接 （第一次写没想出来，毕竟是第一次遇见四维dp） 1.问题分析 利用y总的dp问题分析方法： 集合f(a,b,c,d)的含义为：两次分别走到(a,b),(c,d)两点。 性质为max。 集合的划分： 1.可以划分成四个部分1.f(a-1,b,c-1,d)，2.f(a-1,b,c,d-1)，3.f(a,b-1