# DP patterns— [Notes]

2 min readAug 2, 2023

· 0/1 Knapsack

· Unbounded knapsack

· Fibonacci

· LCS — Longest common subsequence

∘ Longest Palindromic Subsequence

· LIS — Longest increasing subsequence

· Kadane’s algorithms

· Matrix Chain Multiplication

· Rod cutting

· DP on trees

· DP with bit-masking

· Digit DP

· DP on graphs

· Sum over Subsets

· DP on Grid

· Best time to buy and sell stocks

· Unique google questions

· TODO/Sort

# 0/1 Knapsack

- 0/1 knapsack → Code
- Subset sum → Code
- Equal sum partition / 416. Partition Equal Subset Sum → Code
- Count of subset sum → Code
- Minimum subset sum diff (with all positive numbers) → Code
- Count the number of subset with a given difference → Code
- 494. Target Sums (Numbers are +ves, Target can be +ve/-ve) →
**Code** - 🔴[TODO] 2035. Partition Array Into Two Arrays to Minimize Sum Difference (with negative numbers) → Code

Note: This is a hard problem and not a straightforward DP Problem. Dependent problem — Men in Middle. Refer below videos

# Unbounded knapsack

- Rod cutting (Max Cost)→ Code
- 1547. Minimum Cost to Cut a Stick → Code
- Coin change I → Code
- 518. Coin Change II (
*number of combinations that make up that amount)*→ Code - 🔴[TODO] Maximum Ribbon Cut → Code

# Fibonacci

# LCS — Longest common subsequence

- Longest common subsequence (LCS) → Code
- 😵🤩[Revise — Recursive approach] Longest common substring → Code
- Print LCS → Code
- Length of Shortest common super-sequence → Code
- Print Shortest common super-sequence → Code
- Minimum Number of Insertion and Deletion to convert String a to String b → Code
- 🔴[TODO] Edit Distance

## Longest Palindromic Subsequence

# LIS — Longest increasing subsequence

# Kadane’s algorithms

# Matrix Chain Multiplication

- MCM → Code
- 🔴[TODO] MCM Bottom Up
- Print MCM
- Palindrome Partitioning → Recursive + Memo Code
- 🔴[TODO] Palindrome Partitioning → Bottom Up code
- Evaluate Expression to True Boolean Parenthesization Recursive → Code