C# solution based on StoryPKU's C++ DP Solution


  • 0
    D

    This was a very clever 2-dimensional DP solution. I converted it to C# from StoryPKU's post. I have the complexity ~ O(N^3) k, i, j. It is polynomial time, at least, and is decent for small n.
    This is actually a very complicated, but concise, DP solution.

    The algorithm goes something like this:

    • Initialize DP to -1

    • Set value @ (0,0) equal to input's (0,0) value

    • Set maximum path length twice the maximum path length so that two full paths along k - i and k - j respectively can be developed

    • For each path of length k create a new DP using the results from the previous DP

      • Explore all possibilities of paths k-i and k-j taking the maximum value and storing it in new DP[i,j] for each i,j <= k
      • Prior to iterating to next path of length k, set previous DP to current DP
    • Return max of DPn and 0

    Interesting notes:

    • Don't under-estimate the importance of prefilling the DP array with -1. This allows us to determine when we are blocked completely on a given path of length k versus a path that isn't blocked but just doesn't have any cherries (cherries = 0).

    • Pay attention to the recurrence relation between i,j and k-i and k-j. Can you explain it?

    • Nice try StoryPKU on trying to make it intuitive, but I believe the intuition is still lying with you on this one :-) It is definitely a brilliant solution (just no so much intuitive).


     public class Solution
     {
        private void Fill(int[,] source, int n, int value)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    source[i, j] = value;
                }
            }
        }
    
        public int CherryPickup(int[,] grid)
        {
            int n = grid.GetUpperBound(0) + 1;
            // 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.
            int[,] dp = new int[n, n];//Initial DP
    
            Fill(dp, n, -1);
    
            dp[0, 0] = grid[0, 0]; // length k = 0
    
            // maxK: number of steps from (0, 0) to (n-1, n-1).
            int maxK = (n - 1) << 1;
    
            for (int k = 1; k <= maxK; k++)
            { // for every path k
                int[,] curr = new int[n, n];//Create a DP for this path
    
                Fill(curr, n, -1);
    
                // one path of length k arrive at (i, k - i) 
                for (int i = 0; i < n && i <= k; i++)
                {
                    // another path of length k arrive at (j, k - j)
                    for (int j = 0; j < n && j <= k; j++)
                    {
    
                        if ((k - i < n && grid[i, k - i] < 0) || (k - j < n && grid[j, k - j] < 0))
                        { // both paths needs to be able to pass-through
                            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 && j > 0)
                        {
                            cherries = Math.Max(cherries, dp[i - 1, j - 1]);
                        }
                        if (i > 0)
                        {
                            cherries = Math.Max(cherries, dp[i - 1, j]);
                        }
                        if (j > 0)
                        {
                            cherries = Math.Max(cherries, dp[i, 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). 
                        if (k - i < n) 
                        {
                            cherries += grid[i, k - i]; 
                        }
                        if(k - j < n)
                        {
                            cherries += (i == j ? 0 : grid[j, k - j]);
                        }
                                                                       
                        curr[i, j] = cherries;
                    }
                }
                dp = curr;//Set previous DP to this DP
            }
    
            return Math.Max(dp[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.