C++ DP solution


  • 7
    J

    It is the same as two path start from (0, 0) to (n-1, n-1)
    dp[x1][x2] means two length p path , currently one arrived at [..., x1] , the other is at [..., x2], the max value we can get

    loop on length p, update max.

    bottom to up, updated to use one n*n array.

    class Solution {
    public:
        int cherryPickup(vector<vector<int>>& grid) {
            int N = grid.size();
            int P_LEN = N + N - 1;
            vector<vector<int> > dp = vector<vector<int>>(N, vector<int>(N, -1));
            dp[0][0] = grid[0][0];
            
            for (int p = 2; p <= P_LEN; p++) {//p is the length of the path
                for (int x1 = N - 1; x1 >= 0; x1--) {
                    for (int x2 = x1; x2 >= 0; x2--) {
                        int y1 = p - 1 - x1;
                        int y2 = p - 1 - x2;
                        if (y1 < 0 || y2 < 0 || y1 >= N || y2 >= N)
                            continue;
                        if (grid[y1][x1] < 0 || grid[y2][x2] < 0) {
                            dp[x1][x2] = -1;
                            continue;
                        }   
                        int best = -1, delta = grid[y1][x1];
                        if (x1 != x2)
                            delta += grid[y2][x2];
                        if (x1 > 0 && x2 > 0 && dp[x1 - 1][x2 - 1] >= 0) //from left left
                            best = max(best, dp[x1 - 1][x2 - 1] + delta);
                        if (x1 > 0 && y2 > 0 && dp[x1 - 1][x2] >= 0) //from left up
                            best = max(best, dp[x1 - 1][x2] + delta);
                        if (y1 > 0 && x2 > 0 && dp[x1][x2 - 1] >= 0) //from up left
                            best = max(best, dp[x1][x2 - 1] + delta);
                        if (y1 > 0 && y2 > 0 && dp[x1][x2] >= 0) //from up up
                            best = max(best, dp[x1][x2] + delta);
                        dp[x1][x2] = best;
                    }
                }
            }
            return dp[N - 1][N - 1] < 0 ? 0 : dp[N - 1][N - 1];
        }
    };
    

  • 0
    H

    This is clever! Thanks!

    One minor suggestion: we could easily remove the copy operation of "dp1 = dp2", by creating two references (or pointers) and flip their values at each iteration.

    And looking at it more carefully, I think we could use only one dp matrix instead of two (dp1/dp2)?


  • 0
    V

    @Heart135 I guess you're referring to dp[x1][y1][x2][y2]. Then the space complexity will be O(n^4). While if using a flipper like p&1 and ~p&1, we can reducce the space complexity to O(n^2).


  • 0
    H

    @Victorcxq
    (I might be too sleepy and talking nonsense at the moment. ;))
    I thought we could use a single dp[x1][x2], but change the two for-loops for x1 and x2 to be decreasing. Does that make sense?


  • 0
    S

    Single DP Array

    class Solution {
    public:
        int cherryPickup(vector<vector<int>>& grid) {
            int n = grid.size();
            vector<vector<int>> dp(n, vector<int>(n, -1));
            dp[0][0] = grid[0][0];
            
            for (int k = 1; k < 2 * n - 1; k++) {
                vector<vector<int>> curr(n, vector<int>(n, -1));
                for (int i = 0; i < n && i <= k; i++) {
                    for (int j = 0; j < n && j <= k; j++) {
                        if (grid[i][k - i] < 0 || grid[j][k - j] < 0) continue;
                        
                        int t = dp[i][j];
                        
                        if (i > 0) t = std::max(t, dp[i - 1][j]);
                        if (j > 0) t = std::max(t, dp[i][j - 1]);
                        if (i > 0 && j > 0) t = std::max(t, dp[i - 1][j - 1]);
                        if (t < 0) continue;
                        t += grid[i][k - i] + (i == j ? 0 : grid[j][k - j]);
                        
                        curr[i][j] = t;
                    }
                }
                
                dp = std::move(curr);
            }
            
            return std::max(dp[n-1][n-1], 0); 
        }
    };
    

  • 0
    V

    @Heart135 I don't think so... Maybe you can write down your code to test it.
    FYI, as you mentioned before, a modified version of this solution using a flipper as below:

    class Solution {
    public:
        int cherryPickup(vector<vector<int>>& grid) {
            int n = grid.size();
            // for each path, it will end up with 2*n - 2
            int plen = 2 * n - 2;
            int dp[2][n][n];
            // notice that we may use the same index in dp[p&1] and dp[~p&1]
            // we need to initialize the matrix using -1 to avoid mistakes ((x1,x2) may not be reachable)
            for (int i = 0; i<2; i++)
            {
                for (int j = 0; j<n; j++)
                {
                    for (int k = 0; k<n; k++) dp[i][j][k] = -1;
                }
            }
            dp[0][0][0] = grid[0][0];
            dp[1][0][0] = grid[0][0];
            // use a flipper: p&1 as p, ~p&1 as p-1
            // loop over different length
            for (int p = 1; p <= plen; p++)
            {
                for (int x1 = 0; x1 < n; x1++)
                {
                    for (int x2 = x1; x2 < n; x2++)
                    {
                        int y1 = p - x1, y2 = p - x2;
                        if (y1 < 0 || y2 < 0 || y1 >= n || y2 >= n) continue;
                        if (grid[x1][y1] < 0 || grid[x2][y2] < 0)
                        {
                            dp[p&1][x1][x2] = -1;
                            continue;
                        }
                        int best = -1, delta = grid[x1][y1];
                        if (x1 != x2) delta += grid[x2][y2];
                        // (up, up), (up, left), (left, up), (left, left)
                        if (x1 > 0 && x2 > 0 && dp[~p&1][x1 - 1][x2 - 1] >= 0) best = max(best, dp[~p&1][x1 - 1][x2 - 1] + delta);
                        if (x1 > 0 && y2 > 0 && dp[~p&1][x1 - 1][  x2  ] >= 0) best = max(best, dp[~p&1][x1 - 1][  x2  ] + delta);
                        if (y1 > 0 && x2 > 0 && dp[~p&1][  x1  ][x2 - 1] >= 0) best = max(best, dp[~p&1][  x1  ][x2 - 1] + delta);
                        if (y1 > 0 && y2 > 0 && dp[~p&1][  x1  ][  x2  ] >= 0) best = max(best, dp[~p&1][  x1  ][  x2  ] + delta);
                        // update the value
                        dp[p&1][x1][x2] = best;
                    }
                }
            }
            return dp[plen&1][n-1][n-1] < 0? 0 : dp[plen&1][n-1][n-1];
        }
    };
    

    @storypku you still use a curr[n][n]... I don't think it's a single version.
    @jordandong Great solution! Thanks much for sharing it with us.


  • 0
    H

    @storypku The solution you posted still has to create a new matrix |curr| at each step.

    The following solution eliminates that:

        int cherryPickup(vector<vector<int>>& grid) {
          int d = grid.size();
          int p_len = 2 * d - 1;
    
          // state[x1][x2]: the max cherry number two paths of length p can collect.
          // One path is <{0,0} ... {p - x1 - 1, x1}>; the other is
          // <{0, 0} ... {p - x2 - 1, x2}>.
          vector<vector<int>> state(d, vector<int>(d, -1));
    
          state[0][0] = grid[0][0];
    
          for (int p = 2; p <= p_len; ++p) {
            for (int x1 = min(p,d) - 1; x1 >= 0; --x1) {
              for (int x2 = min(p,d) - 1; x2 >= x1; --x2) {
                int y1 = p - x1 - 1;
                int y2 = p - x2 - 1;
    
                if (y1 < 0 || y2 < 0 || y1 >= d || y2 >= d)
                  continue;
    
                if (grid[y1][x1] == -1 || grid[y2][x2] == -1) {
                  state[x1][x2] = -1;
                  continue;
                }
    
                int gain = (x1 == x2) ? grid[y1][x1] : grid[y1][x1] + grid[y2][x2];
    
                int value = -1;
                if (x1 > 0 && state[x1-1][x2] >= 0) {
                  value = max(state[x1-1][x2] + gain, value);
                }
    
                if (x2 > 0 && state[x1][x2-1] >= 0) {
                  value = max(state[x1][x2-1] + gain, value);
                }
    
                if (x1 > 0 && x2 > 0 && state[x1-1][x2-1] >= 0) {
                  value = max(state[x1-1][x2-1] + gain, value);
                }
    
                if (state[x1][x2] >= 0) {
                  value = max(state[x1][x2] + gain, value);
                }
                state[x1][x2] = value;
              }
            }
          }
    
          return max(state[d-1][d-1], 0);
        }
    

  • 0
    V

    @Heart135 I see. You're right. Because dp[i][j] depends on dp[i-1][j], dp[i][j-1], dp[i-1][j-1], if we carefully update the matrix from bottom right corner to top left corner, we will need only one matrix.


  • 0
    R

    hi
    my understanding:
    if we use 4-dimention, dp[x1][y1][x2][y2]

    max(
    dp[x1-1][y1][x2-1][y2] , (from left,left)
    dp[x1][y1-1][x2][y2-1] , (from up, up)
    dp[x1-1][y1][x2][y2-1] , (from left, up)
    dp[x1][y1-2][x2-1][y2] , (from up, left)
    ) + grid[x1][y1] + grid[x2][y2]

    in the code, why can dp1[x1-1][x2-1] represent left, left
    seems reduce y axis? but how does it work?

    thanks


  • 0
    V

    @reliveinfire the tricky part is due to the difference between matrix indices and coordinates. If you simply write an index for matrix grid, like grid[i][j], it means row i and column j. But row <--> y axis, column <--> x axis.


  • 0
    R

    @Victorcxq ok , but not pretty sure,
    why dp1[x1-1][x2-1] can represent dp[x1-1][y1][x2-y][y2],

    looks like rolling dp, reduce the y1/y2


  • 1
    V

    @reliveinfire given fixed length of path p, given x1, x2, we can calculate the corresponding y1 = p - x1 and y2 = p - x2. If y1 and y2 is not out of range, then both paths are legal paths. The key is to understand why we loop over different length of paths.


  • 0
    R

    @Victorcxq
    thanks, i understand.
    below is my understanding:

    p is len of dp2
    p' is len of dp1

    for the loop, p' = p -1 (the loop difference is 1, dp1 is previous loop)
    p = x1 + y1
    dp2[x1], when p is constant, we can have y1 = p -x1

    for dp1[x1]
    y1' = p' - x1,
    y1' = (p-1) - x1
    y1' = y1 -1


Log in to reply
 

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