Complete explanation from a noob in DP


  • 0
    L

    If you are one of the experts who can solve the hard DP problems, you may ignore this. However, if you are like me, who couldn't solve this before reading Cormen, you are at the right place :).

    Thanks to the gentleman who figured out it was analogous to the problem from Cormen: http://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/CRLS-DynamicProg.pdf

    Like any DP problem, the first idea is to find a recursive pattern so that you could come up with a DP-based solution later. My thinking was to create a recursive equation such as: 1,3,5,8 : find the max considering 1 and not considering 1 for the first ballon and so on and so forth. However, the discussion here and referring to the solution of the matrix chain multiplication changed the idea. What we need to note is:

    a. Any balloon may be first or last ; there is no pattern such as keeping min first or last.
    b. If you find max for the first balloon, that solution will be used for building a global max.
    c. The solution sounds recursive.

    Let us try to build up a recursive equation from scratch and then move to solving it using memoization and then bottom-up dp. We should be certain that a recursive solution with O(n!) would give TLE in LeetCode. Now, coming back to the question: assume that an intermediate element k that will be a partition for setting up the recursion. So what we want is :

    a. Find a position k between i and j that is optimal
    b. Find the recursive equation around this assumption

    For all k -> i..j
    max = Math.max(max, max( T(arr,i,k) + T(arr,k+1,j) + (balloon_cost_of_i-1balloon_cost_of_kballoon_cost_of_j)))

    the last part of the recurrence could be understood in terms of matrices. One can look at the link https://youtu.be/GMzVeWpyTN0?t=453 to see what I mean.

    Following code shows a memoization technique. There are other dp solutions that should be self-explanatory after reading this(I guess :)).

      public int maxCoins(int[] nums)
      {
        int[] arr = new int[nums.length + 2];
        arr[0] = 1;
        arr[arr.length - 1] = 1;
        for (int i = 0; i < nums.length; i++)
        {
          arr[i + 1] = nums[i];
        }
        int[][] dp = new int[arr.length][arr.length];
        return helper(arr, 1, arr.length - 1, dp);
      }
    
    
    
      private int helper(int[] nums, int i, int j, int[][] dp)
      {
        if (i == j)
        {
          return 0;
        }
        else if (dp[i][j] != 0)
        {
          return dp[i][j];
        }
        int max = Integer.MIN_VALUE;
        for (int k = i; k < j; k++)
        {
          helper(nums, i, k, dp);
          helper(nums, k + 1, j, dp);
          max =
              Math.max(helper(nums, i, k, dp) + helper(nums, k + 1, j, dp)
                  + nums[i - 1] * nums[k] * nums[j], max);
        }
        dp[i][j] = max;
        return max;
      }
    

Log in to reply
 

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