Mastering Dynamic Programming: Types, Patterns & Practice Questions

Dynamic Programming (DP) is a powerful technique used to solve problems with overlapping subproblems and optimal substructure. Below is a structured guide for solving each type, with patterns and 5 representative LeetCode problems per category.

---

1. 0/1 Knapsack DP

✅ When to Use:

• Choose or skip items.

• Once an item is taken, it can't be reused.

⚖️ Pattern:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i]] + val[i])

🔹 Steps:

1. Define dp[i][w] = max value using first i items with capacity w.

2. Base case: dp[0][w] = 0

3. Iterate i from 1 to n, and w from 0 to capacity.

⚡ Problems:

• 416. Partition Equal Subset Sum

• 494. Target Sum

• 1049. Last Stone Weight II

• 474. Ones and Zeroes

• 198. House Robber (Variant)

---

2. Unbounded Knapsack DP

✅ When to Use:

• You can take the same item multiple times.

⚖️ Pattern:

dp[w] = max(dp[w], dp[w - wt[i]] + val[i])

🔹 Steps:

1. Use 1D dp of size W+1.

2. Outer loop on items, inner loop on weights.

⚡ Problems:

• 322. Coin Change

• 518. Coin Change II

• 279. Perfect Squares

• 343. Integer Break

• 377. Combination Sum IV

---

3. Linear DP (Fibonacci Style)

✅ When to Use:

• Each state depends only on last 1-2 (or k) states.

⚖️ Pattern:

dp[i] = max(dp[i-1], nums[i] + dp[i-2])

🔹 Steps:

1. Identify base cases.

2. Use rolling variables or full DP array.

⚡ Problems:

• 70. Climbing Stairs

• 198. House Robber

• 213. House Robber II

• 1137. N-th Tribonacci Number

• 746. Min Cost Climbing Stairs

---

4. Interval DP

✅ When to Use:

• Problem involves splitting/merging subarrays or segments.

⚖️ Pattern:

dp[i][j] = min/max over dp[i][k] + dp[k][j] + cost(i,j)

🔹 Steps:

1. Sort the array if needed.

2. Build DP table bottom-up over interval length.

⚡ Problems:

• 312. Burst Balloons

• 1000. Minimum Cost to Merge Stones

• 132. Palindrome Partitioning II

• 1547. Minimum Cost to Cut a Stick

• 1039. Minimum Score Triangulation of Polygon

---

5. Tree/Graph DP

✅ When to Use:

• DP over a tree structure or graph with topological order.

⚖️ Pattern:

dp[node] = function of dp[children]

🔹 Steps:

1. Use DFS to traverse tree.

2. At each node, compute DP from children.

⚡ Problems:

• 337. House Robber III

• 834. Sum of Distances in Tree

• 124. Binary Tree Maximum Path Sum

• 968. Binary Tree Cameras

• 329. Longest Increasing Path in a Matrix

---

6. Bitmask / Digit DP

✅ When to Use:

• Bitmask: Subsets, permutations with memory of state.

• Digit: Count numbers under digit constraints.

⚖️ Bitmask Pattern:

dp[mask][i] = min cost of visiting set mask ending at i

⚖️ Digit Pattern:

dp[pos][tight][leadingZero] = count

⚡ Problems:

• 943. Find the Shortest Superstring

• 847. Shortest Path Visiting All Nodes

• 526. Beautiful Arrangement

• 233. Number of Digit One

• 1012. Numbers With Repeated Digits

---

7. 2D Grid/String DP

✅ When to Use:

• Substring/subsequence/2D matrix traversal problems.

⚖️ Pattern:

dp[i][j] = function(dp[i-1][j], dp[i][j-1], ...) depending on characters

🔹 Steps:

1. Set up 2D array with base cases.

2. Fill based on string/grid transitions.

⚡ Problems:

• 1143. Longest Common Subsequence

• 72. Edit Distance

• 97. Interleaving String

• 115. Distinct Subsequences

• 221. Maximal Square

---

🔪 Pro Tip:

Before jumping to code:

1. Can you define state variables?

2. Can you write a recurrence?

3. Is there optimal substructure and overlap?

If yes to all: DP is likely your tool.

---

Let me know if you want code templates or problem walkthroughs!

Unbounded KnapSack with Order (Review)

class Solution {
public:
    int countWays(vector<int>& nums, int target) {
        if (target == 0) return 1;
        int total = 0;
        for (int num : nums) {
            if (num <= target) {
                total += countWays(nums, target - num);
            }
        }
        return total;
    }

    int combinationSum4(vector<int>& nums, int target) {
        return countWays(nums, target);
    }
};