Hái anh đào (Cherry Pickup) trong C++

Lưới N x N: 0=trống, 1=anh đào, -1=gai. Từ (0,0) đi xuống/phải đến (N-1,N-1), rồi về (0,0) lên/trái. Hái anh đào tối đa (ô 1 biến thành 0 sau khi hái). Không có đường thì 0.

Ví dụ

Lưới 3x3 cho trước → kết quả 5.

DP 3 chiều

Xét 2 người đi cùng lúc từ (0,0) đến (N-1,N-1) (tương đương đi rồi về). Trạng thái dp[r1][c1][c2], r2 = r1+c1-c2. Chuyển trạng thái: mỗi người đi xuống hoặc phải. Cộng anh đào ở 2 vị trí (trừ khi trùng).

Chương trình C++

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

int dir[2][2] = {{1,0},{0,1}};
const int INF = 1e9;

class Solution {
    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;
        if(r1<0||c1<0||r2<0||c2<0||r1>=n||r2>=n||c1>=n||c2>=n) return -INF;
        if(grid[r1][c1]==-1 || grid[r2][c2]==-1) return -INF;
        if(r1==n-1 && c1==n-1 && r2==n-1 && c2==n-1) return grid[r1][c1];
        if(dp[r1][c1][c2] != -1) return dp[r1][c1][c2];
        int ret = grid[r1][c1];
        if(r1!=r2 || c1!=c2) ret += grid[r2][c2];
        int best = -INF;
        for(int k=0; k<2; k++) {
            best = max(best, solve(r1+dir[k][0], c1+dir[k][1], c2+1, grid));
            best = max(best, solve(r1+dir[k][0], c1+dir[k][1], c2, grid));
        }
        return dp[r1][c1][c2] = ret + best;
    }
public:
    int cherryPickup(vector<vector<int>>& grid) {
        memset(dp, -1, sizeof(dp));
        return max(0, solve(0,0,0,grid));
    }
};

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