经典的递推。设数字数组是\(a\)，而\(dp_{ij}\)是从这一步到末尾的路程中，高木将比西片高出多少分。那么，如果这一步轮到西片走，他的策略是：

dp[i][j] = a[i+1][j] - dp[i+1][j] if a[i+1][j] > a[i][j+1] else a[i][j+1] - dp[i][j+1]

高木同学的策略是:

dp[i][j] = max(a[i+1][j] + dp[i+1][j], dp[i][j+1] + a[i][j+1])

求得dp[1][1]即可。

Code:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll a[1005][1005], dp[1005][1005], n, m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
    for(int i=n;i>=1;i--) for(int j=m;j>=1;j--)
    {
        if(i==n&&j==m) continue;
        if((i+j)%2) // nishikata
        {
            if(i==n) {dp[i][j] = dp[i][j+1] - a[i][j+1]; continue;}
            if(j==m) {dp[i][j] = dp[i+1][j] - a[i+1][j]; continue;}
            dp[i][j] = a[i+1][j] > a[i][j+1] ? dp[i+1][j] - a[i+1][j]  : dp[i][j+1] - a[i][j+1];                    
        }
        else // takagi-san
        {
            if(i==n) {dp[i][j] = dp[i][j+1] + a[i][j+1]; continue;}
            if(j==m) {dp[i][j] = dp[i+1][j] + a[i+1][j]; continue;}
            dp[i][j] = max(a[i+1][j] + dp[i+1][j], dp[i][j+1] + a[i][j+1]);
        }
    }
    cout<<dp[1][1];
} 

递推 挺经典

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll a[1005][1005], dp[1005][1005], n, m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
for(int i=n;i>=1;i--) for(int j=m;j>=1;j--)
{
if(i==n&&j==m) continue;
if((i+j)%2) // nishikata
{
if(i==n) {dp[i][j] = dp[i][j+1] - a[i][j+1]; continue;}
if(j==m) {dp[i][j] = dp[i+1][j] - a[i+1][j]; continue;}
dp[i][j] = a[i+1][j] > a[i][j+1] ? dp[i+1][j] - a[i+1][j] : dp[i][j+1] - a[i][j+1];

}
else // takagi-san
{
if(i==n) {dp[i][j] = dp[i][j+1] + a[i][j+1]; continue;}
if(j==m) {dp[i][j] = dp[i+1][j] + a[i+1][j]; continue;}
dp[i][j] = max(a[i+1][j] + dp[i+1][j], dp[i][j+1] + a[i][j+1]);
}
}
cout<<dp[1][1];
}