solution

方格取数，经典的动态规划问题，但有所不同。这里可以向上走，也要求不能重复取数。对于这个不同也很好处理，只需要多开一维记录当前格子从哪个方向转移，就可以避免类似刚从上面过来又往上走的问题。

所以，我们设 $f_{i, j, k}$ 表示取数到 $(i, j)$ 时的最大值，$k=0$ 表示从左转过来的，$k=1$ 表示从上转过来的，$k=2$ 表示从下转过来的。

绿色是当前格子，绿色根据 $k$ 是由黄色转移到的，黄色是由红色转移得到，下面是对应的三种情况。

• $k=0$ 时，$f_{i, j, 0} = \max(f_{i, j-1, 0}, f_{i, j-1, 1}, f_{i, j-1, 2})$。

for (int i=1; i<=n; i++)
      for (int j=1; j<=m; j++)
			f[i][j][0]=max({f[i][j-1][0], f[i][j-1][1], f[i][j-1][2]})+a[i][j];

• $k=1$ 时，$f_{i, j, 1} = \max(f_{i, j-1, 0}, f_{i, j-1, 1})$。

for (int i=2; i<=n; i++)
      for (int j=1; j<=m; j++)
			f[i][j][1]=max(f[i-1][j][0], f[i-1][j][1])+a[i][j];

• $k=2$ 时，$f_{i, j, 2} = \max(f_{i, j-1, 0}, f_{i, j-1, 2})$。

for (int i=n-1; i>=1; i--)
      for (int j=1; j<=m; j++)
			f[i][j][2]=max(f[i+1][j][0], f[i+1][j][2])+a[i][j];

因为有负数，所以实现的时候要注意初值设极小值。

code

#include <bits/stdc++.h>
using namespace std;
long long n, m, a[1005][1005], f[1005][1005][3];
int main () {
	cin >> n >> m;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			cin >> a[i][j];
	memset(f, -0x3f, sizeof f);
	f[1][1][0]=f[1][1][1]=f[1][1][2]=a[1][1];
	for (int j=1; j<=m; j++) {
		for (int i=1; i<=n; i++)
			f[i][j][0]=max({f[i][j-1][0], f[i][j-1][1], f[i][j-1][2]})+a[i][j];
		for (int i=2; i<=n; i++)
			f[i][j][1]=max(f[i-1][j][0], f[i-1][j][1])+a[i][j];
		for (int i=n-1; i>=1; i--)
			f[i][j][2]=max(f[i+1][j][0], f[i+1][j][2])+a[i][j];
	}
	cout << max({f[n][m][0], f[n][m][1], f[n][m][2]});
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e3+10;
LL a[N][N], up[N], down[N], f[N];
int main()
{
    int n, m; scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%lld", &a[i][j]);
    f[1]=a[1][1]; for(int i=2; i<=n; i++) f[i]=f[i-1]+a[i][1];
    for(int i=2; i<=m; i++)
    {
        memset(up, -0x3f, sizeof(up)); memset(down, -0x3f, sizeof(down));
        up[n]=f[n]+a[n][i]; down[1]=f[1]+a[1][i]; 
        for(int j=n-1; j>=1; j--) up[j]=max(up[j+1], f[j])+a[j][i];
        for(int j=2; j<=n; j++) down[j]=max(down[j-1], f[j])+a[j][i];
        for(int j=1; j<=n; j++) f[j]=max(up[j], down[j]);
    }
    printf("%lld\n", f[n]); return 0;
}