金币馅饼

按照列枚举，根据题意可知，每列更新过一次之后，这列就不会再更新；保证了无后效性；
注意有些点是走不到的，不能用这些点更新别的点；
dp[i][j]表示到达第i行第j列的金币数量

#include<bits/stdc++.h>
using namespace std;
const int maxn=200;
int dp[maxn][maxn],mp[maxn][maxn];
int r,c;
int main()
{
    cin>>r>>c;
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
            cin>>mp[i][j];
    }

    memset(dp,-1,sizeof(dp));  dp[1][1]=0;
    for(int j=1;j<=c;j++)//列
    {
        for(int i=1;i<=r;i++)//行
        {
            dp[i][j]=max(max(dp[i][j],dp[i+1][j-1]),max(dp[i-1][j-1],dp[i][j-1]));
            if(dp[i][j]!=-1) dp[i][j]+=mp[i][j];//如果==-1，说明走不到，！=-1说明能到达
        }
    }
    cout<<dp[r][c];
}