1. 问题一

方格图中，从左上角到右下角，途中最多能够获取的最大值，或者最小的代价

2. DP分析

状态表示f[i][j]
集合：从(1,1)到(i,j)所有路径的集合
属性：所有路径max/min

状态转移f[i][j] = (max|min)(f[i][j-1], f[i-1][j]) + w[i][j]，根据上一步的来源，从左边空格或者上边空格转移过来

实际实现过程中，如果结果是最大值，一般不用特殊处理边界；如果结果是最小值，边界可能需要特殊处理

// 最大值
for(int i = 1; i <= r; i++){
    for(int j = 1; j <= c; j++){
        s[i][j] = max(s[i][j-1], s[i-1][j]) + a[i][j];
    }
}
// 最小值
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++)
    {
        if(i == 1){
            s[i][j] = s[i][j-1] + a[i][j];
        } else if(j == 1){
            s[i][j] = s[i-1][j] + a[i][j];
        } else {
            s[i][j] = min(s[i][j-1], s[i-1][j]) + a[i][j];
        }
    }
}

问题二

方格图中，需要走多次路径，同时多次行走的路径之间有影响；不能分开多次单独求解，出现局部最优解非全局最优？
典型例题：https://www.acwing.com/problem/content/1029/
状态表示f[x1][y1][x2][y2]的集合：从(1,1),(1,1)到(x1, y1), (x2, y2)所有路径的集合
状态属性：max/min等
状态划分：f[x1][y1][x2][y2] = max(s[x1][y1-1][x2][y2-1], s[x1][y1-1][x2-1][y2], s[x1-1][y1][x2][y2-1], s[x1-1][y1][x2-1][y2]) + ret

if(x1 == x2 && y1 == y2){
    ret = a[x1][y1];
} else {
    ret = a[x1][y1] + a[x2][y2];
}
s[x1][y1][x2][y2] = max(s[x1][y1-1][x2][y2-1], s[x1][y1-1][x2-1][y2]);
s[x1][y1][x2][y2] = max(s[x1-1][y1][x2][y2-1], s[x1][y1][x2][y2]);
s[x1][y1][x2][y2] = max(s[x1-1][y1][x2-1][y2], s[x1][y1][x2][y2]);