算法竞赛进阶指南， 270 页， 线性DP
本题要点：
1、状态表示：
每一条路径的第i步和所在的坐标点 (x, y) 的关系 x + y == i + 2;
因此，每条路径的三个未知量(i, x, y) 可以用两个 未知量来(i, x)表示 // y == i + 2 - x
dp[i][x1][x2] 表示两条路径长度i,而且第一条路径末尾在x1行，第二条在x2 行，取得的最大值
2、转态转移：
根据路径的走向，分类讨论：
1）第一条：往右， 第二条：往右
2）第一条：往右， 第二条：往下
3）第一条：往下， 第二条：往右
4）第一条：往下， 第二条：往下
//下面以 右右 为例子：
if(x1 == x2) //走到相同的格子，只叠加一次相应的格子 w[x1][y1 + 1]
{dp[i + 1][x1][x2] = max(dp[i + 1][x1][x2], dp[i][x1][x2] + w[x1][y1 + 1]);
}else{dp[i + 1][x1][x2] = max(dp[i + 1][x1][x2], dp[i][x1][x2] + w[x1][y1 + 1] + w[x2][y2 + 1]);
}
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 60;
int dp[MaxN * 2][MaxN][MaxN]; //dp[i][x1][x2] 表示两条路径长度i,而且第一条路径末尾在x1行，第二条在x2 行，取得的最大值
int m, n; //n行， m列
int w[MaxN][MaxN];int main()
{
scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
scanf("%d", &w[i][j]);}}memset(dp, 0, sizeof(dp));//边界dp[0][1][1] = w[1][1];int y1, y2;for(int i = 0; i < n + m - 2; ++i){
for(int x1 = 1; x1 <= n && x1 <= i + 1; ++x1){
for(int x2 = 1; x2 <= n && x2 <= i + 1; ++x2){
y1 = i + 2 - x1, y2 = i + 2 - x2;//两条路径都往右走if(x1 == x2) //走到相同的格子，只叠加一次相应的格子 w[x1][y1 + 1]{
dp[i + 1][x1][x2] = max(dp[i + 1][x1][x2], dp[i][x1][x2] + w[x1][y1 + 1]);}else{
dp[i + 1][x1][x2] = max(dp[i + 1][x1][x2], dp[i][x1][x2] + w[x1][y1 + 1] + w[x2][y2 + 1]);}//x1 往右， x2往下 （有往下走的判断是否能往下走）if(x2 < n){
if(x1 == x2 + 1) //走到相同的格子{
dp[i + 1][x1][x2 + 1] = max(dp[i + 1][x1][x2 + 1], dp[i][x1][x2] + w[x1][y1 + 1]); }else{
dp[i + 1][x1][x2 + 1] = max(dp[i + 1][x1][x2 + 1], dp[i][x1][x2] + w[x1][y1 + 1] + w[x2 + 1][y2]); }}//x1 往下， x2往右if(x1 < n){
if(x2 == x1 + 1) //走到相同的格子{
dp[i + 1][x1 + 1][x2] = max(dp[i + 1][x1 + 1][x2], dp[i][x1][x2] + w[x2][y2 + 1]); }else{
dp[i + 1][x1 + 1][x2] = max(dp[i + 1][x1 + 1][x2], dp[i][x1][x2] + w[x1 + 1][y1] + w[x2][y2 + 1]); }}//x1 往下， x2往下if(x1 < n && x2 < n){
if(x1 == x2) {
dp[i + 1][x1 + 1][x2 + 1] = max(dp[i + 1][x1 + 1][x2 + 1], dp[i][x1][x2] + w[x1 + 1][y1]); }else{
dp[i + 1][x1 + 1][x2 + 1] = max(dp[i + 1][x1 + 1][x2 + 1], dp[i][x1][x2] + w[x1 + 1][y1] + w[x2 + 1][y2]); }}}}}printf("%d\n", dp[n + m - 2][n][n]);return 0;
}/* 3 3 0 3 9 2 8 5 5 7 0 *//* 34 */