Annotated C++ DP Solution


  • 14
    S

    It takes me quite some time to understand the DP solution to this problem this afternoon.

    So I post the solution here with annotations for anyone who might find helpful.

    Updated Dec 05, 2017. Thanks for @张博文 @xu8908 @szyyn95 for pointing out the overflow case.

    class Solution {
    public:
        int cherryPickup(vector<vector<int>>& grid) {
            int n = grid.size();
            // dp holds maximum # of cherries two k-length paths can pickup.
            // The two k-length paths arrive at (i, k - i) and (j, k - j), 
            // respectively.
            vector<vector<int>> dp(n, vector<int>(n, -1));
    
            dp[0][0] = grid[0][0]; // length k = 0
            
            // maxK: number of steps from (0, 0) to (n-1, n-1).
            const int maxK = 2 * (n - 1); 
            
            for (int k = 1; k <= maxK; k++) { // for every length k
                vector<vector<int>> curr(n, vector<int>(n, -1));
            
                // one path of length k arrive at (i, k - i) 
                for (int i = 0; i < n && i <= k; i++) {
                    if ( k - i >= n) continue;
                    // another path of length k arrive at (j, k - j)
                    for (int j = 0; j < n && j <= k; j++) {
                        if (k - j >= n) continue;
                        if (grid[i][k - i] < 0 || grid[j][k - j] < 0) { // keep away from thorns
                            continue;
                        }
                        
                        int cherries = dp[i][j]; // # of cherries picked up by the two (k-1)-length paths.
                        
                        // See the figure below for an intuitive understanding
                        if (i > 0) cherries = std::max(cherries, dp[i - 1][j]);
                        if (j > 0) cherries = std::max(cherries, dp[i][j - 1]);
                        if (i > 0 && j > 0) cherries = std::max(cherries, dp[i - 1][j - 1]);
                        
                        // No viable way to arrive at (i, k - i)-(j, k-j).
                        if (cherries < 0) continue;
                        
                        // Pickup cherries at (i, k - i) and (j, k -j ) if i != j.
                        // Otherwise, pickup (i, k-i). 
                        cherries += grid[i][k - i] + (i == j ? 0 : grid[j][k - j]);
                    
                        curr[i][j] = cherries;
                    }
                }
                dp = std::move(curr); 
            }
            
            return std::max(dp[n-1][n-1], 0); 
        }
    };
    

    0_1512312388737_cherry-pickup.jpg


  • 0
    O

    very nice solution!


  • 0

    why do not

    grid[i][k - i] < 0
    

    overflow when i = 0 && k > n?


  • 0
    X

    @张博文 yeah,so i put

    if(k-i>=N||k-j>=N||grid[i][k-i]<0||grid[j][k-j]<0)continue;
    

    instead


  • 1
    S

    Translate your code in Java and works perfectly.
    Also, still wondering why would your original code work without checking y coordinate overflow, as somebody else pointed out. Did I miss anything?

    class Solution {
        public int cherryPickup(int[][] grid) {
            int n = grid.length;
            if (n == 0) return 0;
            int[][] DP = new int[n][n];
            for (int[] row : DP) Arrays.fill(row, -1);
            int max_len = n*2 - 2; //max possible path length
            DP[0][0] = grid[0][0];
            
            //DP[i][j] in loop k: when the length of path is k, 
            //the x coord of path 1 is i, the x coord of path 2 is j,
            //what's the max num of cherries?
            for (int k = 1; k <= max_len; k++){
                int[][] temp = new int[n][n];
                for (int[] row : temp) Arrays.fill(row, -1);
                
                for (int i = 0; i <= Math.min(k, n - 1); i++){
                    for (int j = 0; j <= Math.min(k, n - 1); j++){
                        if (k - i >= n || k - j >= n) continue; //y coord overflow
                        if (grid[i][k - i] == -1 || grid[j][k - j] == -1) continue;
                        
                        int cur_cherry = DP[i][j];
                        if (i > 0) cur_cherry = Math.max(cur_cherry, DP[i - 1][j]);
                        if (j > 0) cur_cherry = Math.max(cur_cherry, DP[i][j - 1]);
                        if (i > 0 && j > 0) cur_cherry = Math.max(cur_cherry, DP[i - 1][j - 1]);
                        if (cur_cherry < 0) continue; //no possible way to here
                        
                        if (i == j) temp[i][j] = cur_cherry + grid[i][k - i];
                        else temp[i][j] = cur_cherry + grid[i][k - i] + grid[j][k - j];
                    }
                }
                DP = temp;
            }
            return Math.max(0, DP[n - 1][n - 1]);
        }
    }
    

  • 0
    S

    @张博文 I have the solution updated to take the "overflow" case into consideration.

    As to why the program don't overflow when i = 0 && k > n, I think this is related to how C++ handles 2-D array in in memory.
    In C++, 2-D array was stored continuously just like 1-D array.
    So, suppose we have an array[3][3], the element array[2][3] is equivalent to array[3][0].

    Example:

    [story@StoryTeller:~]$ cat hello.cpp
    #include <cstdio>
    int main() {
        int arr[3][3] = {};
        arr[2][3] = 5;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                printf("arr[%d][%d]=%d\n", i, j, arr[i][j]);
            }
        }
        printf("%d\n", arr[2][3]);
    
        printf("%d\n", arr[3][0]);
        return 0;
    }
    
    [story@StoryTeller:~]$ g++ hello.cpp -g
    hello.cpp:4:5: warning: array index 3 is past the end of the array (which contains 3 elements)
          [-Warray-bounds]
        arr[2][3] = 5;
        ^      ~
    hello.cpp:3:5: note: array 'arr' declared here
        int arr[3][3] = {};
        ^
    hello.cpp:10:20: warning: array index 3 is past the end of the array (which contains 3 elements)
          [-Warray-bounds]
        printf("%d\n", arr[2][3]);
                       ^      ~
    hello.cpp:3:5: note: array 'arr' declared here
        int arr[3][3] = {};
        ^
    2 warnings generated.
    

  • 0

    I very appreciate that you can give such detailed explanation
    thanks a lot


  • 0
    D

    Nice, the DP takes some time to understand. I converted it to C# and needed to account for the array bounds (overflow). I will post that in C# and give some credit to you for idea, thanks.


  • 1
    D

    @szyyn95 said in Annotated C++ DP Solution:

    if (k - i >= n || k - j >= n) continue; //y coord overflow

    Open Source versions of C++ allow that (there's lots of C++ solution on LeetCode not checking array/vector bounds). On the other hand, for Microsoft C++, you must explicitly turn off the checking with compiler options. If you were run the original in Visual Studio C++, it would also crash when k >= n;


  • 0
    D

    @dingess Also "hackers" love to go past the end of an array :-)


  • 0
    S

    @dingess Thanks for response. Yeah I rarely code in C++ so have totally no idea of this.


  • 0
    K
    This post is deleted!

  • 0
    Q

    @storypku Great post. Due to symmetry,

    for (int j = 0; j <= Math.min(k, n - 1); j++)
    can be changed to
    for (int j = i; j <= Math.min(k, n - 1); j++)


Log in to reply
 

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