10-liner DP with time/space optimization and why greedy doesn't work


  • 0

    First of all, greedy method does not work here. That is:

    Maximizing the first one-way for cherries does NOT guarantee maximized cherries for round-trip.

    The reason is that the problem allows only shortest path moving and greedy method does not do a good overall planning.

    Counter Example:
    0 1 -1
    1 1 -1
    1 1 0

    If the first one-way goes along the red path for maximal 3 cherries, it splits the remaining 2 cherries into opposite sides of the diagonal which is impossible for round trip to pick up all cherries.

    Define DP variable: so we have to plan the round trip altogether. Note that the path direction is irrelevant to the problem and we are forced to move only on shortest paths.

    Define

    dp[i][j][L] = the max cherries picked up from (0,0) along two shortest paths reaching (i,L-i) and (j,L-j), respectively.

    Note that each path length is exactly L, so the answer is to compute dp[n-1][n-1][2*(n-1)].

    To reach cells (i,L-i) and (j,L-j), you have to reach their left or top cells with any combination, which leads to the DP equation:

    dp[i][j][L] = max(dp[i-a][j-b][L-1] for a, b = 0 or 1) + grid[i][L-i] + grid[j][L-j]
    

    To optimize time/space complexity, note that

    • (i,j) is symmetric, so why not just compute for i<=j.
    • (i,j,L) has constraint: max(L-n+1,0) <= i <= j <= min(L,n-1).
    • dp[][][L] depends on only dp[][][L-1], so no need to allocation O(n) space in L dimension.
    int cherryPickup(vector<vector<int>>& grid) 
    {
        int n = grid.size();
        vector<vector<int>> cur(n, vector<int>(n,-1)), next = cur;
        cur[0][0] = grid[0][0];
    
        // cur[i][j] is set for i<=j
        auto Cur = [&](int i, int j) { return 0<=min(i,j) && max(i,j)<n? cur[min(i,j)][max(i,j)] : -1; };        
    
        for (int L = 1; L <= 2*(n-1); L++, cur = next)        
            for (int i = max(L-n+1,0); i <= min(L,n-1); i++)
                for (int j = i; j <= min(L,n-1); j++) 
                {   // max cherries for path length L-1 before arriving (i,k-1) and (j,k-j)
                    int curMax = max(max(Cur(i,j), Cur(i-1,j)), max(Cur(i,j-1),Cur(i-1,j-1)));
                    // max cherries for path length L reaching (i,k-1) and (j,k-j)
                    next[i][j] = (grid[i][L-i]>=0 && grid[j][L-j]>=0 && curMax>=0)? curMax+grid[i][L-i]+(i!=j)*grid[j][L-j] : -1;   
                }
    
        return max(Cur(n-1,n-1), 0);         
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.