C++で解くチェリーピックアップ問題：往復移動でチェリーを最大化する動的計画法

問題概要

N × N のグリッドが与えられ、各マスにはチェリーが置かれています。マスに入っている値は次のいずれかです。

• 0 ― マスは空であり、自由に通過できます
• 1 ― マスにチェリーがあり、通過時に回収できます
• -1 ― マスにトゲがあり、通行を妨げられます

以下のルールに従って、回収できるチェリーの数を最大化することを目指します。

• (0, 0) から出発し、「右」または「下」への移動のみで有効な経路をたどって (N-1, N-1) まで進む
• (N-1, N-1) に到達した後、今度は「左」または「上」への移動のみで (0, 0) まで戻る
• チェリーのあるマスを通ると、そのチェリーを回収し、そのマスは空（値 0）になる
• (0, 0) から (N-1, N-1) への有効な経路が存在しない場合、回収できるチェリーは 0 個となる

たとえば、入力が次のような場合を考えてみましょう。

このとき出力は 5 になります。(0, 0) から下・下・右・右と進んで (2, 2) に至るまでに 4 個のチェリーを回収でき、この時点でグリッドは次のようになります。

続けて、左・上・上・左と進んで (0, 0) に戻る途中で、さらに 1 個のチェリーを回収できます。よって合計で 5 個のチェリーが回収可能です。

解法のアプローチ

この問題は、「行き」と「帰り」の 2 つの経路を同時に進むものと考えると効率よく解けます。2 人が同じステップ数で移動する場合、両者の位置は常に r1 + c1 = r2 + c2 を満たすため、状態として (r1, c1, c2) の 3 つの値を管理すれば十分です。これをメモ化再帰（動的計画法）で実現します。手順は以下のとおりです。

• サイズ 2 × 2 の方向配列 dir := {{1, 0}, {0, 1}} を定義する
• INF := 10^9 とする
• サイズ 51 × 51 × 51 のメモ化配列 dp を定義する
• 関数 solve() を定義する。引数は r1, c1, c2 と二次元配列 &grid
• n := grid のサイズ、r2 := r1 + c1 − c2、ret := 0 とする
• m := （n が非ゼロなら grid[0] のサイズ、それ以外は 0）
• r1 < 0 または c1 < 0 または r2 < 0 または c2 < 0、あるいは r1 ≥ n または r2 ≥ n または c1 ≥ m または c2 ≥ m の場合、
  • -INF を返す
• grid[r1][c1] == -1 または grid[r2][c2] == -1 の場合、
  • -INF を返す
• r1 == r2 かつ c1 == c2 かつ r1 == n−1 かつ c1 == m−1 の場合（ゴールに両者が到着）、
  • grid[r1][c1] を返す
• dp[r1][c1][c2] ≠ -1 の場合（計算済み）、
  • dp[r1][c1][c2] を返す
• ret := ret + grid[r1][c1]
• r1 == r2 かつ c1 == c2 の場合（同一マス）、何もしない（二重カウント防止）
• それ以外の場合、
  • ret := ret + grid[r2][c2]
• temp := -INF とする
• k := 0 から k < 2 の間、k を 1 ずつ増やしながら繰り返す：
  • temp := max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2 + 1, grid))
  • temp := max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2, grid))
• dp[r1][c1][c2] = ret + temp として返す
• main 関数では以下を行う：
• dp をすべて -1 で埋める
• ret := solve(0, 0, 0, grid)
• max(0, ret) を返す

それでは、以下の実装例を見て理解を深めましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
int dir[2][2] = {{1, 0}, {0, 1}};
const int INF = 1e9;
class Solution {
public:
    int dp[51][51][51];
    int solve(int r1, int c1, int c2, vector<vector<int>>& grid){
        int n = grid.size();
        int r2 = r1 + c1 - c2;
        int ret = 0;
        int m = n? grid[0].size() : 0;
        if(r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0 || r1 >= n || r2 >= n || c1 >= m || c2 >= m) return -INF;
        if(grid[r1][c1] == -1 || grid[r2][c2] == -1) return -INF;
        if(r1 == r2 && c1 == c2 && r1 == n - 1 && c1 == m - 1)return grid[r1][c1];
        if(dp[r1][c1][c2] != -1) return dp[r1][c1][c2];
        ret += grid[r1][c1];
        if(r1 == r2 && c1 == c2){
           }else ret += grid[r2][c2];
           int temp = -INF;
           for(int k = 0; k < 2; k++){
           temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2 + 1, grid));
           temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2, grid));
        }
        return dp[r1][c1][c2] = ret + temp;
    }
    int cherryPickup(vector<vector<int>>& grid) {
        memset(dp, -1, sizeof(dp));
        int ret = solve(0, 0, 0, grid);
        return max(0, ret);
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{0,1,-1},{1,0,-1},{1,1,1}};
    cout << (ob.cherryPickup(v));
}

入力

{{0,1,-1},{1,0,-1},{1,1,1}}

出力

5