题解 | #金币馅饼#

这么多人写DP，那我写一个记忆化搜索的，刚开始跑的时候忘记加限制条件，注意有些地方是跑不到的

using namespace std;
#define INF 1000000
int n,m;
int mp[110][110],dp[110][110],mp1[110][110];
int dx[3]={-1,0,1};
int dy[3]={1,1,1};

bool judge(int x,int y){
	if(x<1||x>n||y<1||y>m) return false;
	else return true;
}

int dfs(int x,int y){
	//cout<<x<<" "<<y<<endl;
	if(x==n&&y==m){
		//cout<<n<<" "<<m<<endl;
		return mp[x][y];
	}else if(x!=n&&y==m){
		return 0;
	}
	if(dp[x][y]!=0){
		return dp[x][y];
	}
	int ans=mp[x][y];
	for(int i=0;i<3;++i){
		int xx=x+dx[i];
		int yy=y+dy[i];
		//cout<<x<<" "<<y<<" "<<ans<<endl;
		if(judge(xx,yy)&&(m-yy)>=(n-xx)){//注意限制条件
			ans=max(ans,dfs(xx,yy)+mp[x][y]);
		}
	}
	dp[x][y]=ans;
	//cout<<x<<" "<<y<<" "<<ans<<endl;
	return dp[x][y];
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>mp[i][j];
		}
	}
	memset(dp,0,sizeof(dp));
	dfs(1,1);
	cout<<dp[1][1]<<endl;
}