この問題はDPにより解くことができます。

\(\mathrm{DP}[i][j][d]\) を「直前に方向 \(d\) に移動し、\(i\) 行 \(j\) 列に到達した時点でのスコアの最大値」とし、配るDPを考えます。求める答えは \(\max_{j,d} \mathrm{DP}[N][j][d]\) です。

\(\mathrm{DP}[i][j][d]\) からは、次の移動方向を \(d'\) として \(\mathrm{DP}[i+1][j+k][d']\) の高々 3 通りへ遷移します。\(d=d'=右下\) 及び \(d=d'=左下\) のときには遷移できないことに注意してください。

全ての \(j,d\) で \(\mathrm{DP}[N][j][d]\) を求めるために考慮する必要がある状態数は \(O(NM)\) であり、遷移 \(O(1)\) であることから \(O(NM)\) でこの問題を解くことができました。

\(\mathrm{DP}[i+1][*][*]\) を求めるために必要な情報は \(\mathrm{DP}[i][*][*]\) のみであることから、以下の実装例では \(i\) を明示的にキーに持たないようにしています。また添字の順序が \([j][d]\) ではなく \([d][j]\) となっています。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<vector<long long>> g(n, vector<long long>(m));
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin >> g[i][j];
    }
  }

  vector<vector<long long>> dp(3);
  for(int i=0; i<3; i++){
    dp[i] = g[0];
  }

  for(int i=1; i<n; i++){
    vector<vector<long long>> new_dp(3, vector<long long>(m, -1e18));
    for(int j=0; j<m; j++){
      for(int dd=-1; dd<=1; dd++){
        for(int kk=-1; kk<=1; kk++){
          int d = dd + 1;
          int k = kk + 1;
          if((dd < 0 && kk < 0) || (dd > 0 && kk > 0)){
            continue;
          }
          if(!(0 <= j+dd && j+dd < m)){
            continue;
          }
          new_dp[d][j+dd] = max(new_dp[d][j+dd], dp[k][j] + g[i][j+dd]);
        }
      }
    }
    swap(dp, new_dp);
  }

  long long ans=-1e18;
  for(int d=0; d<3; d++){
    for(int j=0; j<m; j++){
      ans = max(ans, dp[d][j]);
    }
  }
  cout << ans << endl;
}

実装例 (Python)

N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(N)]

dp = [G[0] for _ in range(3)]

for i in range(1, N):
  new_dp = [[0] * M for _ in range(3)]
  for j in range(M):
    for d in range(-1, 2):
      for k in range(-1, 2):
        if (d < 0 and k < 0) or (d > 0 and k > 0):
          continue
        if not (0 <= j+d < M):
          continue
        new_dp[d][j+d] = max(new_dp[d][j+d], dp[k][j] + G[i][j+d])
  dp = new_dp

print(max(max(dpi) for dpi in dp))