方格取数是个老题，生命力极强，最早出现在2000年noip，20年后的2020年CSP普及组又考了，本文围绕方格取数的三种变化，讲解一些基本解题方法，包括暴力搜索，记忆化搜索，动态规划等。
一、基本型
最简单的，简单到算法竞赛的题库都不屑收录，leetcode有此题：
64. 最小路径和
给定一个包含非负整数的 m*n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
题目简化以后就是从左上角到右下角找一条路径，路径上的数和最小。
1、先来暴力搜
考察右下角，只能从它上面或者左面过来，哪条路的和比较小，就选哪条，其它格子也都一样。
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
class Solution {
public:
int minPathSumUtil(vector<vector<int> >& grid, int x, int y){
if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size()){
//超出范围了，返回一个大数，min的时候肯定不会选择它。
return 0x7fffffff;
}
if (x == 0 && y == 0){
return grid[0][0];
}
return min(minPathSumUtil(grid, x, y - 1), minPathSumUtil(grid, x - 1, y)) + grid[x][y];
}
int minPathSum(vector<vector<int> >& grid) {
return minPathSumUtil(grid, grid.size() - 1, grid[0].size() - 1);
}
};
2、记忆化搜索
上面代码会超时，因为很多格子重复计算了，比如一个中间的格子，从下面来也算一次，从右面来也算一次。加速办法是如果第一次算好就存起来，下次直接用。如下代码可通过leetcode：
class Solution {
int f[200][200];
public:
int minPathSumUtil(vector<vector<int> >& grid, int x, int y){
if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size()){
return 0x7fffffff;
}
if (f[x][y] == -1){
f[x][y] = min(minPathSumUtil(grid, x, y - 1), minPathSumUtil(grid, x - 1, y)) + grid[x][y];
}
return f[x][y];
}
int minPathSum(vector<vector<int> >& grid) {
memset(f, -1, sizeof(f));
f[0][0] = grid[0][0];
return minPathSumUtil(grid, grid.size() - 1, grid[0].size() - 1);
}
};
3、简单动态规划(dp)
一般来说记忆话搜索和简单动态规划可以相互转化，此题应用初级动态规划，设计状态为f(i,j)，表示从左上角到坐标为(i,j)的格子最小路径的和，显然f(m,n)就是最终结果。状态转移方程：
f(i,j) = min(f(i-1, j), f(i, j-1)) + grid(i,j)
f(i-1,j)是它上面格子的状态，f(i,j-1)是左边格子的状态，一个格子只能从上或者左转移过来。f(i,j)同时具备子问题最优解和无后效性。
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
class Solution {
int f[200][200];
public:
int minPathSum(vector<vector<int> >& grid) {
f[0][0] = grid[0][0];
//先填充第0行，不能从上面来，只能从左边转移过来
for(int j = 1; j < grid[0].size(); j++){
f[0][j] = f[0][j-1] + grid[0][j];
}
//再填充第一列，不能从左边来，只能从上边来
for(int i = 1; i < grid.size(); i++){
f[i][0] = f[i-1][0] + grid[i][0];
}
for(int i = 1; i < grid.size(); i++){
for(int j = 1; j < grid[0].size(); j++){
f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i][j];
}
}
return f[grid.size()-1][grid[0].size()-1];
}
};
此处可以优化一下空间，变二维数组为一维数组，也叫滚动数组，因为f(i,j)只和f(i-1,j)，f(i,j-1)有关，也就是只和它左边或者上面1行有关，上面1行的上面存多了也没什么用。
class Solution {
int f[200];
public:
int minPathSum(vector<vector<int> >& grid) {
f[0] = grid[0][0];
//先填充第0行，不能从上面来，只能从左边转移过来
for(int j = 1; j < grid[0].size(); j++){
f[j] = f[j-1] + grid[0][j];
}
for(int i = 1; i < grid.size(); i++){
f[0] += grid[i][0];
for(int j = 1; j < grid[0].size(); j++){
f[j] = min(f[j-1], f[j]) + grid[i][j];
}
}
return f[grid[0].size()-1];
}
};
二、双人型
基本型太简单了，考试肯定不考，需要增加难度：不是求一条路径，而是两条，数被一条路径取走以后就变成0，另一条路径就不能取了。题目是NOIP2000提高组真题，详见洛谷p1004。
两个人跑路比一个人难多了，上面说的方法统统失效，搜索不会写，记忆化也无从谈起，简单dp找不出状态。既然简单dp不行，那就来个复杂dp。还是状态转移，本题状态比原来更复杂一些，但还是能转移的，用一个思维数组表示状态：
f(i,j,k,l)表示第一条路径走到(i,j),第二条路径走到(k,l)时，取得数的和最大值。(i,j)只能从(i-1,j)和(i,j-1)转移而来，(k,l)同理，所以f(i,j,k,l)只能从以下4种状态转移而来：
1、f(i-1,j,k-1,l)
2、f(i-1,j,k,l-1)
3、f(i,j-1,k-1,l)
4、f(i,j-1,k,l-1)
转移方程：等一下，既然知道怎么转移了，直接撸代码吧，老写转移方程干什么？近代西方数学极速发展的一个重要原因，就是因为引入了统一符号。方程写出来，非常有助于人的思考。做动态规划题，必须严格写出转移方程，才能真正提高算法水平，否则做了也是白做，遇到新题还是两眼一抹黑。
言归正传，写方程：
f(i,j,k,l) = max(f(i-1,j,k-1,l), f(i-1,j,k,l-1), f(i,j-1,k-1,l), f(i,j-1,k,l-1)) + a(i,j) + a(k,l)
注意边界条件，ij和kl相同时，加一次即可，因为两条路径公共部分的数只能被一条路径取走。
#include <cstdio>
#include <algorithm>
#define MAX 9
using namespace std;
int n, g[MAX+1][MAX+1], f[MAX+1][MAX+1][MAX+1][MAX+1];
int main(){
scanf("%d", &n);
int x, y, v;
do{
scanf("%d%d%d", &x, &y, &v);
g[x][y] = v;
} while(x != 0 || y != 0 || v != 0);
f[1][1][1][1] = g[1][1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= i + j - 1; k++){
int l = i + j - k;
f[i][j][k][l] = max(f[i-1][j][k-1][l], max(f[i-1][j][k][l-1], max(f[i][j-1][k-1][l], f[i][j-1][k][l-1])));
f[i][j][k][l] += (i == k) ? g[i][j] : g[i][j] + g[k][l];
}
}
}
printf("%d\n", f[n][n][n][n]);
return 0;
}
注意上面k和l的取值，两条路径同步进行，i+j总是等于k+l，并且k取1到i+j-1，超过这个范围没有意义。
三、新瓶旧酒三方向
双人型方格取数沉寂了整整20年后，2020年csp普及组又考方格取数，这次是一条路径，但行进方向由原来的下和右变成左，下，右。详见洛谷p7074
先粗略估计一下，最优解大概是一种蛇形路线，先下来，再上去，再下来，再上去......有了上面介绍的两种方格取数的经验，三方向就有据可循了。先利用基本型的经验，坚定此题可用dp解决的信心；再利用双人型的经验和启发，确定状态。基本型只两种来源方向，左和上，比较一下取最大值就能得到最终结果并保存起来；现在多了一个来源方向，下，根据双人型的经验，把状态数组再加一维，变成f(i,j,k)，用第三维k记录来源方向，考虑转移方程：
f(i,j,上) = max(f(i-1,j,上), f(i-1,j,左)) + a(i,j)
f(i,j,左) = max(f(i,j-1,左), f(i,j-1,上), f(i,j-1,下)) + a(i,j)
f(i,j,下) = max(f(i+1,j,左), f(i+1,j,下)) + a(i,j)
考察第一行，除了第一个格子，都不可能从上面来，从上面来的值是负无穷；从左面来和左面的有关，一时间无法确定；从下面来也不好确定。
考察第一列，除了第一个元素，都不可能从左面来，从左面来的值是负无穷；从上面来的结果肯定可以根据转移方程计算，因为它上面的格子的上，左都可确定；从下面来的结果也是负无穷，因为是第一列，不可能从下面来。此时第一列的三种状态全部确定，从第二列开始，每一列的每个方格都从左边的列转移而来。
考察第二列第一个方格，上面来确定是负无穷，左面可转移而来；再考察第二列所有方格，和第一个方格类似，从上往下填充，上面可转移而来；左面可转移而来，因为它左面第一列的三种状态全部确定；
考察第二列最后一行元素，从左面来可确定，从下面来可确定负无穷，再考察第二列从下往上填充，下面也可转移而来，此时，第二列所有3种状态全部填充完毕。以后3～m列依此类推，最后max(f(n,m,左),f(n,m,上))就是答案。
#include <cstdio>
#include <algorithm>
#include <climits>
#define MAX 1000
typedef long long ll;
using namespace std;
int g[MAX+1][MAX+1];
ll f[MAX+1][MAX+1][3];
int n, m;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &g[i][j]);
f[i][j][0] = f[i][j][1] = f[i][j][2] = LLONG_MIN;
}
}
//0表示从上面来，1从下面来，2从左面来
//先初始化第一个格子，让他能从上面，左面来
f[1][1][0] = f[1][1][2] = g[1][1];
//初始化第一列从上面来的值，从下面和从左面都不可能，都是负无穷
for(int i = 2; i <= n; i++){
f[i][1][0] = f[i-1][1][0] + g[i][1];
}
//此时第一列三种状态全部初始化完毕，后面每列都右它左边的列转移而来
for(int j = 2; j <= m; j++){
for(int i = 1; i <= n; i++){
//转移从左边来的值
f[i][j][2] = max(max(f[i][j-1][0], f[i][j-1][1]), f[i][j-1][2]) + g[i][j];
if(i > 1){//下面填充从上面来的，第一行肯定是负无穷，跳过
f[i][j][0] = max(f[i-1][j][0], f[i-1][j][2]) + g[i][j];
}
}
//下面从下往上递推转移从下边来的值
for(int i = n-1; i >= 1; i--){
f[i][j][1] = max(f[i+1][j][1], f[i+1][j][2]) + g[i][j];
}
}
printf("%lld\n", max(f[n][m][0], f[n][m][2]));
return 0;
}
如代码所示，对于每一列，从上到下推一遍，得到上和左，再从下到上推一遍，得到下。三种状态全部确定后，推下一列。
最后，动态规划最关键的就是设计状态，写出转移方程，看到转移方程可以启发出递推方法，在编码的时候看着转移方程编也不会出错，必须掌握这种技术。
