Dynamic Programming

Dynamic Programming (DP)

  • Check if the given problem can be solved using recursion. If so, then observe if DP can help or not.

  • Even the maximum profit scheduling problem is a recursion: do you want to take current job or not. Some times, we may need to sort the data. Here we sorted in endTime order.

    Use binary search if already sorted data exists, instead of using treemap just for the sake of floorKey operation. It will help with time.

Problem Solution & Details
Maximal Square Difficult to come up with the logic. Solution
Largest rectangle Problem Histogram based solution
Largest magic square  
Edit Distance  
Maximum Profit in Job Scheduling DP solution - Sort it and get into Knapsack style problem
Palindrome partitioning  
Longest Valid Parentheses  
Best time to buy and sell stock IV A little tough
Bursting balloons Choose k as the last balloon burst in range [i, j]. Boundaries i-1 and j+1 are guaranteed alive because they belong to an outer subproblem and are burst even later. Score = dp(i, k-1) + nums[i-1]*nums[k]*nums[j+1] + dp(k+1, j).
Wild card matching problem Solution
Russian doll envelopes LIS variant: First sort the data based on one field, then find the LIS based on the second field.
Largest divisible subset LIS variant: first sort and then check LIS property based on whether one is divisible by another.
Partition Equal Subset Sum Similar to knapsack
Minimum string containing both strings as subsequences Using DP solution for Longest Common Subsequnce, construct the DP table. Now come in the reverse order of the strings and DP table: i=m-1, j=n-1. If the chars at i and j are same, then our superstring will include only one of them. Else, if dp[i][j-1] > dp[i-1][j], then take str2(j--), else str1(i--) and add to the result string. Because, for constructing the original DP table, we would have deleted str2(j) and the remaining substrings have higher DP value. So we must include this uncommon char. Keep proceeding. At the end add remaining chars if any from both strings.
Unlimited quantities knapsack A slight modification of 0-1 knapsack. In the memoization manner for 0-1 knapsack, we do take or no-take. Modify the take where instead of incrementing the i value, keep using the same i for recursion. int take = dp(i, capacity - wt[i]) instead of take = dp(i+1, capacity - wt[i]). See below for memoization .
Minimum char additions to make a String palindrome First calculate length of the longest plaindromic SUBSEQUENCE. Now you have to add the letters that are not forming the palindrome. Answer is s.length() - lps.
Equal Partition or a target sum The solution uses memoization which needs \(O(n * sum)\) space. But when using tabulation we can reduce it to one row \(O(sum)\). We can loop over the capacity only from right to left. See 1D space DP code.
Minimum Score Triangulation of Polygon Fix two boundary vertices i and j. Try every vertex k between them as the third point of a triangle: score = values[i]*values[k]*values[j] + dp(i,k) + dp(k,j). Memoize on (i,j). Solution
Matrix Chain Multiplication Classic interval DP. For a chain of matrices i..j, try every split point k: cost = dp(i,k) + dp(k+1,j) + dims[i-1]*dims[k]*dims[j]. Memoize on (i,j). Same pattern as polygon triangulation.

Unlimited quantities knapsack 

// Calculate maximum profit for each
// item index and knapsack weight.
for (int i = val.length - 1; i >= 0; i--) {
    for (int j = 1; j <= capacity; j++) {
        int take = 0;
        if (j - wt[i] >= 0) {
            take = val[i] + dp[i][j - wt[i]];
        }
        int noTake = dp[i + 1][j];
        dp[i][j] = Math.max(take, noTake);
    }
}
return dp[0][capacity];

1D Space DP solution 

for j from targetSum down to 0:
    for each num in nums:
        if j >= num: dp[j] = dp[j] || dp[j - num]