Dynamic Programming

0/1 Knapsack Pattern

1. 0/1 Knapsack Problem

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

3. Count Subset Sum

4. Minimum Subset Sum Difference

5. Target Sum

Unbounded Knapsack

1. Core Concept

2. Rod Cutting

3. Coin Change

4. Minimum Coin Change

5. Maximum Ribbon Cut

6. Natarajan's Birthday Bombs

   https://www.interviewbit.com/problems/tushars-birthday-bombs/

Buy and Sell Stocks (State Machines Concept)

1. Buy and Sell Stock with at most 1 Transaction
2. Buy and Sell Stocks with unlimited Transactions
3. Buy and Sell Stocks with a Transaction Fee
4. Buy and Sell Stocks with a cooldown period
5. Buy and Sell Stocks with at most 2 transactions
6. Buy and Sell Stock with at most k transactions

Longest Increasing Subsequence

1. Core Concept
2. Maximum Sum Increasing Subsequence
3. Minimum Deletions to make a Sequence Sorted

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

4. Box Stacking
5. Russian Doll
6. Largest Divisible Subset
7. Longest String Chain
8. Best Team With No Conflict
9. Longest Bitonic Sequence

   Minimum Number of Removals To Make Mountain Array (Very Similar to Bitonic Sequence)

All Possible Cuts in All Possible Intervals For Choosing Last Operation

1. Unique BST Unique BST - Better Solution
2. Tree With Minimum Cost Leaf Nodes

   Explained Here - https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/discuss/339959/One-Pass-O(N)-Time-and-Space
3. Matrix Chain Multiplication
4. Optimal BST
5. Minimum Palindrome Partioning From Leetcode solutions
6. Burst Balloons
7. Merging Stones (Similar to burst balloons)

Kadanes

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

1. Maximum Sum Subarray
2. Maximum Product Subarray

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

1. Best Time to Buy and Sell Stock

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. Longest Common Substring
2. Longest Common Subsequence
3. Shortest Common Supersequence
4. Minimum Deletions & Insertions To Transform a String into another
5. String Interleaving
6. Edit Distance
7. Subsequence Pattern Matching
8. Longest Repeating Subsequence

1-String Problems

1. Longest Palindromic Subsequence
2. Longest Palindromic Substring
3. Minimum Palindrome Partioning

   From Leetcode solutions

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

4. 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

1. Regular Expression Matching
2. Wildcard Matching

Optimal Path To Target

1. Optimal Path To Target

   Includes the Minimum Cost for Tickets Problem

Unique Paths

1. Unique Paths 1

   Unique Paths 1 - Space Optimized
2. Unique Paths 2

   Unique Paths 2 - Space Optimized
3. Minimum Path Sum

Other Problems

1. House Robber

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

2. Dungeon Game

   Dungeon Game Space Optimized - 1D DP table

   Dungeon - Modifying the Input grid directly
3. Cherry Pickup (This has comments explaining the thought process)

   Cherry Pickup - Space Optimized
4. Cherry Pickup 2

   Cherry Pickup 2 - 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.

1. Letter Case Permutations
2. All Path From Source To Target
3. Word Search
4. Generate Parentheses
5. T-9 Keyboard
6. Palindrome Partitioning
7. Sudoku Solver

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

1. Permutations 1
2. Permutations 2
3. N-Queens
4. N-Queens 2
5. Word-Squares - Using Hashmap

   Word-Squares - Using Tries
6. Restore IP Addresses
7. Path Sum 2
8. Gray Code
9. Factor Combinations
10. Robot Room Cleaner

Similar Problems But slightly different

1. Subsets 1 and 2
2. Permutations 1 and 2
3. Combination Sum 1, 2 and 3
4. 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()