README.md

11 - Dynamic Programming

PHASE 11 — DYNAMIC PROGRAMMING (491–500)

Topics Covered

• One-Dimensional DP
• Knapsack and Subset DP
• String DP
• Path Counting and Grid DP
• Memoization and Tabulation

---

Problems List

No.	Problem	Difficulty	Topics	Link
1	Climbing Stairs	Easy	1D DP	Open
2	House Robber	Medium	1D DP	Open
3	Coin Change	Medium	Unbounded Knapsack	Open
4	Longest Increasing Subsequence	Medium	DP, Binary Search	Open
5	Longest Common Subsequence	Medium	String DP	Open
6	Word Break	Medium	String DP	Open
7	Decode Ways	Medium	String DP	Open
8	Unique Paths	Medium	Grid DP	Open
9	Knapsack 0/1	Medium	0/1 Knapsack	Open
10	Edit Distance	Hard	String DP	Open

---

Important Patterns

1D DP

• Use when the state depends only on previous positions
• Often solved with memoization or iterative tabulation
• Good for stair, house, and counting problems

String DP

• Compare prefixes of strings and build answers from smaller prefixes
• Useful for subsequences, decoding, and editing distance problems
• Track decisions with a 2D state

Knapsack Patterns

• 0/1 knapsack chooses each item at most once
• Unbounded knapsack allows repeated use of an item
• Convert optimization into a recurrence over weight or count

Grid DP

• Count paths or ways to move through a matrix
• Use obstacles or boundaries as base cases
• Often reduces to simple tabulation on rows and columns