Dynamic Programming

0/1 Knapsack Pattern

  1. Equal Subset Sum Partition (Also includes Subset Sum - Very Similar)

Unbounded Knapsack

Buy and Sell Stocks (State Machines Concept)

Longest Increasing Subsequence

  1. Minimum Deletions to make a Sequence Sorted

    Classic LIS problem. Find the LIS of the sequence and the deletions = arr.length - LIS.length

All Possible Cuts in All Possible Intervals For Choosing Last Operation

  1. Merging Stones (Similar to burst balloons)

Kadanes

Explanation - https://www.youtube.com/watch?v=86CQq3pKSUw

The best time to buy and sell 1 stock can also be seen as an application of Kadane's algorithm

2-String Problems

Note: Some of these problems can ask for the length/count of the longest/shortest common substring/sequence or it can also ask for the substring/subsequence produced.

1-String Problems

  1. Minimum Palindrome Partioning

    From Leetcode solutions

    (Already posted as part of All Possible Cuts in All Possible Intervals For Choosing Last Operation)

  2. Minimum Insertions To Form a Palindrome

    You can always just find the Longest Palindromic subsequence and use that. str.length - LPS.length will also give you the same answer.

    Similarly, you can also use the Longest Common Subsequence technique. You need to do an LCS on str and str.reverse() and then str.length - LCS(str, str.reverse()) will give you the same answer.

Advanced String DP Problems

Optimal Path To Target

  1. Optimal Path To Target

    Includes the Minimum Cost for Tickets Problem

Unique Paths

Other Problems

  1. House Robber

    This fits into the knapsack category. You either choose a house to rob or you skip the house.

  2. Cherry Pickup (This has comments explaining the thought process)

    Cherry Pickup - Space Optimized

Other Backtracking Problems

Practicing Backtracking problems also helps provide a good foundation and thought process for DP based problems. These are some classic backtracking problems.

The difference between permutations 1 and 2 is that 1 has unique numbers in the input array and 2 has duplicate numbers possible

Similar Problems But slightly different

  1. Palindrome Permutations

    A few neat optimizationz are done in this solution.

    1. We check if we can even compute a palindrome from the given string. If not we immediately return.

    2. If it's an odd length palindrome, we get the mid point character (1 character which only appears once)

    3. We just take half of the remaining characters and compute all permutations on just half the list. When we have a complete permutation we do permutation + mid + permutation.reverse(). This allows us to calculate all possible permutations on just half the string instead of the entire string.

      For even length palindromes mid will be empty so it will essentailly be permutation + permutation.reverse()

Last updated

Was this helpful?