[741. Cherry Pickup] C++ DP and some comments


  • 3

    Thanks for @storypku https://discuss.leetcode.com/topic/112877/annotated-c-dp-solution
    and @jordandong
    https://discuss.leetcode.com/topic/112856/c-dp-solution/2
    who post their solutions.
    And I was thinking about this problem for a whole afternoon and I just wanna add some comments from myself to better understand this problem.

    At first I tried use DFS and separated the question into two parts: from [0,0] to [n-1,n-1] and from [n-1,n-1] to [0,0], but the time limit exceeded.

    Some comments:

    n is the side length of grid.

    First of all, there are two phases, from [0,0] to [n-1,n-1] and from [n-1,n-1] to [0,0]. However, these two paths can be viewed both as from [0,0] to [n-1, n-1], because they are "mirror systematic". What we want is finding out the largest sum of two traverses both from [0,0] and [n-1, n-1].

    Therefore, we use a 2D vector dp to store the largest sum of two paths. dp[i][j] is not so easy to understand, so here I explain i and j as:

    • i: the going-down steps of the first path
    • j: the going-down steps of the second path

    We also know the total steps from [0,0] to [n-1,n-1] is 2n - 2. Suppose the current total steps for each of path are len, then
    for i, the steps that it can go down is min(n-1, len); the same for the j.
    Once we give the current total steps of each path, the final position in the grid of each path can be confirmed, which are grid[i][len - i] and grid[j][len - j]. Therefore, if grid[i][len - i] is -1 or grid[j][len - j] is -1, we can skip and continue to the i++ or j++ in our for loop.

    Each time we increase our total steps by 1, and consider all possible paths in the two "mirror systematic" paths,

    Basic idea is:
    dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + grid[i][len-i] + grid[j][len-j]

    Always remember that in the dp, dp[i][j] is the largest sum of two paths (the collected cherries), i and j is the steps of going-down for the two paths separately. In the grid[i][len-i] is the current position of path i in the grid, because the current total steps is len. The same for grid[j][len-j].

    The following procedures can be checked in the code.

    class Solution {
    public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        if(n == 1) return grid[0][0];
        int steps = 2*n - 2;
    
        for(int len = 1; len <= steps; ++len){
            vector<vector<int>> temp(n, vector<int>(n, -1));
            for(int i = 0; i <= len && i < n; ++i){
                for(int j = 0; j <= len && j < n; ++j){
                    if(grid[i][len -i] < 0 || grid[j][len - j] < 0) continue;
                    int cher = dp[i][j];
                    
                    //three possible cases to reach current position in the two paths.
                    if(i > 0) cher = max(cher, dp[i-1][j]);
                    if(j > 0) cher = max(cher, dp[i][j-1]);
                    if(i > 0 && j > 0) cher = max(cher, dp[i-1][j-1]);
                    
                    if(cher < 0) continue;
                     //if i and j are the same, it means i and j are in the same position in the grid.
                    cher += grid[i][len - i] + (i == j ? 0 : grid[j][len - j]);
                    temp[i][j] = cher;
                }
            }
            dp = move(temp);
        }
        return max(dp[n-1][n-1], 0);
    }
    };

  • 0
    H

    Can you explain why need dp[i-1][j-1]? What I can understand is, dp[i-][j] and dp[i][j-1] are the largest number of cherries for len - 1 steps, but I do not understand why dp[i-1][j-1] also stands for len - 1 steps..


  • 0

    @hpnhxxwn Actually we consider 4 cases:

    dp[i][j]
    dp[i-1][j]
    dp[i][j-1]
    dp[i-1][j-1]

    the 4 directions which the two paths can reach to current positions. I revised the formula and added dp[i][j].


  • 0
    H

    Here is what I thought:
    calculate dp[i][j] from dp[i][j-1] represents two paths that do not meet at the same place after moving one more step.
    calculate dp[i][j] from dp[i-1][j-1] represents two paths that meet at the same place after moving one more step.

    dp[i][j] itself is the result from past iteration of length 1 ~ len - 1, so we factor this in just because we want to pick the maximum.

    Correct me if I'm wrong. Thank you.


  • 0

    @hpnhxxwn I am not sure i understand your idea.
    But i think it does not matter whether they meet at the same place or not.

    As i stated:
    i: the going-down steps of the first path
    j: the going-down steps of the second path

    So if we want the two paths at the status: first path going down for i steps, second path going down for j steps, we have 4 cases:

    1. it is already at the status that we want, which is dp[i][j]

    2. Previously, first path was at status "i-1" and then by going down 1 it becomes "i". Second path is already at status "j"

    3. Previously, second path was at status "j-1" and then by going down 1 it becomes "j". First path is already at status "i"

    4. Previously, first path was at status "i-1" and then by going down 1 it becomes "i". Second path was at status "j-1" and then by going down 1 it becomes "j".

    And we keep updating dp[i][j] because we are extending our total steps.

    The above analysis is my understanding, it might be wrong :-)
    You can also check storypku's draft to help u understand this problem: https://discuss.leetcode.com/topic/112877/annotated-c-dp-solution


  • 0
    R

    @jasonshieh
    i dont understand dp[i-1][j-1], neither.

    is this supposed to be

    max(
    dp[i-1][j-1] + grid[i][len-i] + grid[j][len-j]
    dp[i-1][j] + grid[i][len-i]
    dp[i][j-1] + grid[j][len-j]
    dp[i][j])
    if the dp[i-1][j-1] is the previous status?
    we add two new grid value for dp[i-1][j-1] (move i, move j)
    but the original code, get the max, and add two steps?

    thanks


  • 0
    D
    This post is deleted!

Log in to reply
 

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