记忆化搜索

#include <bits/stdc++.h>
#define ll long long
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 1e3+10 ;
const ll MIN = -LINF;
int g[N][N];
ll f[N][N][3];//由  右 上 下 转移而来 注意开long long
int n,m;

ll dfs(int x,int y,int k){
	if(x<1 or y<1 or x>n or y>m)return MIN; //越界直接返回极小值，代表非法状态转移
	if(f[x][y][k]!=MIN) return f[x][y][k]; //!=极小值，代表被计算过，不必重复计算直接返回 [记忆化]
	
	if(k==0){ // 从左边过来
		f[x][y][k] = max({dfs(x,y-1,0),dfs(x,y-1,1),dfs(x,y-1,2)}) + (ll)g[x][y];
	}
	else if(k==1){ //从上面下来
		f[x][y][k] = max(dfs(x-1,y,0),dfs(x-1,y,1)) + (ll)g[x][y];
	}
	else {    // 从下面上来
		f[x][y][k] = max(dfs(x+1,y,0),dfs(x+1,y,2)) + (ll)g[x][y];
	}
	return f[x][y][k];
}

int main() 
{
	cin >> n >> m;	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >> g[i][j];
	//初始化
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			for(int k=0;k<3;k++)
				f[i][j][k] = MIN;

	f[1][1][0] = (ll)g[1][1];
	f[1][1][1] = (ll)g[1][1];
	
	ll ans = max(dfs(n,m,0),dfs(n,m,1)); //终点只能由左或上转移而来
	
	cout << ans;
	
	return 0;
}

递推DP

#include <bits/stdc++.h>
#define ll long long
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 1e3+10 ;
const ll MIN = -LINF;
int g[N][N];
ll f[N][N][3];//由  右 上 下 转移而来 注意开long long
int n,m;

int main() 
{
	cin >> n >> m;	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >> g[i][j];
	//初始化
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			for(int k=0;k<3;k++)
				f[i][j][k] = MIN;
	
	f[1][1][0] = (ll)g[1][1];
	f[1][1][1] = (ll)g[1][1];
	f[1][1][2] = (ll)g[1][1];
	
	for (int i = 2; i <= n; i++)
		f[i][1][2] = f[i-1][1][2] + g[i][1];
	
	for (int j = 2; 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]}) + (ll)g[i][j];
			f[i][j][1] = max(f[i-1][j][0],f[i-1][j][1]) + (ll)g[i][j];
		}
		for (int i = n-1; i >= 0; i --)
		{
			f[i][j][2] = max(f[i+1][j][0],f[i+1][j][2]) + (ll)g[i][j];
		}
	}
	cout << max(f[n][m][0], f[n][m][1]);
	return 0;
}