> For the complete documentation index, see [llms.txt](https://bytecookie.gitbook.io/dp-interviews/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://bytecookie.gitbook.io/dp-interviews/master.md).

# Dynamic Programming

## 0/1 Knapsack Pattern

1. [0/1 Knapsack Problem](/dp-interviews/notes/0-1knapsack.md)
2. [Equal Subset Sum Partition](/dp-interviews/notes/equal-subset-sum-partition.md) (Also includes Subset Sum - Very Similar)
3. [Count Subset Sum](/dp-interviews/notes/count-subset-sum.md)
4. [Minimum Subset Sum Difference](/dp-interviews/notes/minimum-subset-sum-difference.md)
5. [Target Sum](/dp-interviews/notes/target-sum.md)

## Unbounded Knapsack

1. [Core Concept](/dp-interviews/notes/unbounded-knapsack.md)
2. [Rod Cutting](/dp-interviews/notes/rod-cutting.md)
3. [Coin Change](/dp-interviews/notes/coin-change.md)
4. [Minimum Coin Change](/dp-interviews/notes/minimum-coin-change.md)
5. [Maximum Ribbon Cut](/dp-interviews/notes/max-ribbon-cut.md)
6. [Natarajan's Birthday Bombs](/dp-interviews/notes/natarajans-birthday-bombs.md)

   <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](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Buy-Sell-Stocks/at-most-1-transaction.js)
2. [Buy and Sell Stocks with unlimited Transactions](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Buy-Sell-Stocks/buy-sell-unlimited-transactions.js)
3. [Buy and Sell Stocks with a Transaction Fee](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Buy-Sell-Stocks/buy-sell-transaction-fee.js)
4. [Buy and Sell Stocks with a cooldown period](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Buy-Sell-Stocks/buy-sell-with-cooldown.js)
5. [Buy and Sell Stocks with at most 2 transactions](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Buy-Sell-Stocks/buy-sell-at-most-2-transactions.js)
6. [Buy and Sell Stock with at most k transactions](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Buy-Sell-Stocks/buy-sell-at-most-k-transactions.js)

## Longest Increasing Subsequence

1. [Core Concept](/dp-interviews/notes/longest-increasing-subsequence.md)
2. [Maximum Sum Increasing Subsequence](/dp-interviews/notes/maximum-sum-increasing-subsequence.md)
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](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Box-Stacking/boxStacking.js)
5. [Russian Doll](/dp-interviews/notes/russian-doll.md)
6. [Largest Divisible Subset](/dp-interviews/notes/largest-divisible-subset.md)
7. [Longest String Chain](/dp-interviews/notes/longest-string-chain.md)
8. [Best Team With No Conflict](/dp-interviews/notes/best-team-with-no-conflict.md)
9. [Longest Bitonic Sequence](/dp-interviews/notes/longest-bitonic-sequence.md)

   [Minimum Number of Removals To Make Mountain Array](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Longest-Bitonic-Sequence/minimum-number-of-removals-to-make-mountain-array.js) (Very Similar to Bitonic Sequence)

## All Possible Cuts in All Possible Intervals For Choosing Last Operation

1. [Unique BST](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Unique-BST/unique-bst.js) [Unique BST - Better Solution](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Unique-BST/unique-bst-2.js)
2. [Tree With Minimum Cost Leaf Nodes](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Tree-With-Min-Cost-Leaf-Nodes/min-cost-leaf-nodes-stack.js)

   Explained Here - [https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/discuss/339959/One-Pass-O(N)-Time-and-Space](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/discuss/339959/One-Pass-O%28N%29-Time-and-Space)
3. [Matrix Chain Multiplication](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Matrix-Chain-Multiplication/matrix-chain-multiplication.js)
4. [Optimal BST](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Optimal-BST/optimal-bst.js)
5. [Minimum Palindrome Partioning](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Min-Palindrome-Partitioning/min-palindrome-partitioning-optimized.js) [From Leetcode solutions](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Min-Palindrome-Partitioning/min-palindrome-partitioning-smart.js)
6. [Burst Balloons](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Burst-Balloons/burst-balloons.js)
7. [Merging Stones](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Burst-Balloons/merge-stones.js) (Similar to burst balloons)

## Kadanes

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

1. [Maximum Sum Subarray](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Kadanes/maxSubarrayKadane.js)
2. [Maximum Product Subarray](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Kadanes/maxProductSubarray-elegant.js)

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](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Buy-Sell-Stocks/at-most-1-transaction.js)

## 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](/dp-interviews/notes/longest-common-substring.md)
2. [Longest Common Subsequence](/dp-interviews/notes/longest-common-subsequence.md)
3. [Shortest Common Supersequence](/dp-interviews/notes/shortest-common-supersequence.md)
4. [Minimum Deletions & Insertions To Transform a String into another](/dp-interviews/notes/minimum-insertions-deletions-transform.md)
5. [String Interleaving](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/String-Interleaving/string-interleaving-optimized.js)
6. [Edit Distance](/dp-interviews/notes/edit-distance.md)
7. [Subsequence Pattern Matching](/dp-interviews/notes/subsequence-pattern-matching.md)
8. [Longest Repeating Subsequence](/dp-interviews/notes/longest-repeating-sequence.md)

## 1-String Problems

1. [Longest Palindromic Subsequence](/dp-interviews/notes/longest-palindromic-subsequence.md)
2. [Longest Palindromic Substring](/dp-interviews/notes/longest-palindromic-substring.md)
3. [Minimum Palindrome Partioning](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Min-Palindrome-Partitioning/min-palindrome-partitioning-optimized.js)

   [From Leetcode solutions](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Min-Palindrome-Partitioning/min-palindrome-partitioning-smart.js)

   (Already posted as part of All Possible Cuts in All Possible Intervals For Choosing Last Operation)
4. [Minimum Insertions To Form a Palindrome](https://github.com/vedantb/DP-Interviews/tree/746642c4896349114c442abf9ed439d6490a8193/Minimum-Insertion-To-Form-Palindrome/min-insertion-form-palindrome.js)

   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](/dp-interviews/notes/regular-expression-matching.md)
2. [Wildcard Matching](/dp-interviews/notes/wildcard-matching.md)

## Optimal Path To Target

1. [Optimal Path To Target](/dp-interviews/notes/optimal-path-to-target.md)

   Includes the Minimum Cost for Tickets Problem

## Unique Paths

1. [Unique Paths 1](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Unique-Paths/unique-paths1.js)

   [Unique Paths 1 - Space Optimized](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Unique-Paths/unique-paths1-optimized.js)
2. [Unique Paths 2](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Unique-Paths/Unique-paths-2.js)

   [Unique Paths 2 - Space Optimized](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Unique-Paths/unique-paths-2-optimized.js)
3. [Minimum Path Sum](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Other-Problems/min-path-sum.js)

## Other Problems

1. [House Robber](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Other-Problems/house-robber.js)

   This fits into the knapsack category. You either choose a house to rob or you skip the house.
2. [Dungeon Game](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Other-Problems/dungeon-game.js)

   [Dungeon Game Space Optimized - 1D DP table](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Other-Problems/dungeon-game-space-optimized.js)

   [Dungeon - Modifying the Input grid directly](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Other-Problems/dungeon-game-modify-input.js)
3. [Cherry Pickup](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Other-Problems/cherry-pickup.js) (This has comments explaining the thought process)

   [Cherry Pickup - Space Optimized](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Other-Problems/cherry-pickup-dp.js)
4. [Cherry Pickup 2](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Other-Problems/cherry-pickup-2.js)

   [Cherry Pickup 2 - Space Optimized](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Other-Problems/cherry-pickup-2-optimized.js)

## 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](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/letter-permutations.js)
2. [All Path From Source To Target](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/all-paths-source-to-destination.js)
3. [Word Search](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/word-search.js)
4. [Generate Parentheses](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/generate-parentheses.js)
5. [T-9 Keyboard](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/T9-Keyboard.js)
6. [Palindrome Partitioning](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/palindrome-partitioning.js)
7. [Sudoku Solver](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/sudoku-solver.js)

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](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/permutations-1.js)
2. [Permutations 2](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/permutations-2.js)
3. [N-Queens](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/N-Queens.js)
4. [N-Queens 2](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/N-Queens-2.js)
5. [Word-Squares - Using Hashmap](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/word-squares-hashmap.js)

   [Word-Squares - Using Tries](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/word-squares-trie.js)
6. [Restore IP Addresses](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/restore-ip-addresses.js)
7. [Path Sum 2](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/path-sum-2.js)
8. [Gray Code](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/gray-code.js)
9. [Factor Combinations](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/factor-combinations.js)
10. [Robot Room Cleaner](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/robot-room-cleaner.js)

### Similar Problems But slightly different

1. [Subsets 1 and 2](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/Category1/subsets.js)
2. [Permutations 1 and 2](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/Category1/permutations.js)
3. [Combination Sum 1, 2 and 3](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/Category1/combinationsums.js)
4. [Palindrome Permutations](https://github.com/vedantb/DP-Interviews/tree/90efd4f9bbcb30c6de4a65ba42656380414d250a/Backtracking/Category1/palindrome-permutations.js)

   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()`