เก็บเชอร์รี (Cherry Pickup) ใน C++

ภาพรวมปัญหา

มีกริด N x N ที่มีเชอร์รี แต่ละเซลล์เป็น: 0=ว่าง, 1=มีเชอร์รี, -1=หนามบล็อกทาง ต้องเก็บเชอร์รีสูงสุดโดย:

เริ่ม (0,0) ไป (N-1,N-1) เดินขวา/ล่าง
กลับ (N-1,N-1) ไป (0,0) เดินซ้าย/บน
ผ่านเชอร์รีเก็บได้ (กลายเป็น 0)
ไม่มีทางระหว่าง (0,0) และ (N-1,N-1) → ได้ 0

ตัวอย่าง

Grid 3x3 → Output: 5

แนวทางแก้ปัญหา (DP 3 มิติ)

คิดเป็น 2 คนเดินจาก (0,0) ไป (N-1,N-1) พร้อมกัน (เทียบเท่าการไป-กลับ)
State: (r1, c1, c2) โดย r2 = r1 + c1 - c2
DP[r1][c1][c2] = เชอร์รีสูงสุดจากจุดนี้ไปจนจบ
Transition: ทั้งคู่เดินลงหรือขวา (4 กรณี)
Base case: ถึงจุดสุดท้าย คืนค่า grid[r1][c1]
Memoization ป้องกันคำนวณซ้ำ

ตัวอย่างโปรแกรม

#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)) 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);
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,1,-1},{1,0,-1},{1,1,1}};
    cout << (ob.cherryPickup(v));
}

Input

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