🧠 MASTER GUIDE: Problem-Solving Templates

Each section contains:

• Pattern Name
• Problem Examples
• Key Decisions
• Reusable Recursion/DP Template

---

1️⃣ Take / Not Take Pattern

Base of all subset/knapsack-style problems.

🔹 Problem Types:

• 0/1 Knapsack
• Subset Sum / Count Subsets with Sum
• Target Sum
• Partition Equal Subset
• House Robber

🔹 Template:

int solve(int i, int[] nums, int sum) {
    if (i == nums.length) return base_case;

    // Not take
    int notTake = solve(i + 1, nums, sum);

    // Take if valid
    int take = 0;
    if (nums[i] <= sum)
        take = solve(i + 1, nums, sum - nums[i]);

    return Math.max(take, notTake); // or count, min, etc.
}

---

2️⃣ Unbounded Take / Not Take

Use when elements can be picked multiple times.

🔹 Problem Types:

• Unbounded Knapsack
• Coin Change (Min coins or Total Ways)
• Rod Cutting

🔹 Template:

int solve(int i, int[] nums, int target) {
    if (i == nums.length) return base_case;

    // Take: stay on same i
    int take = Integer.MAX_VALUE;
    if (nums[i] <= target)
        take = 1 + solve(i, nums, target - nums[i]);

    // Not take: move to next i
    int notTake = solve(i + 1, nums, target);

    return Math.min(take, notTake);
}

---

3️⃣ DP on Subsequences

LCS, LIS, Edit Distance — comparing sequences.

🔹 Problem Types:

• Longest Common Subsequence
• Edit Distance
• Longest Palindromic Subsequence
• Minimum Insertions/Deletions

🔹 Template:

int solve(int i, int j, String s1, String s2) {
    if (i == s1.length() || j == s2.length()) return base_case;

    if (s1.charAt(i) == s2.charAt(j))
        return 1 + solve(i + 1, j + 1, s1, s2);

    return Math.max(
        solve(i + 1, j, s1, s2),
        solve(i, j + 1, s1, s2)
    );
}

---

4️⃣ DP on Index and State

Track more than just index — also a "state" (like previous selection, count, etc.)

🔹 Problem Types:

• Longest Increasing Subsequence
• Paint House / Job Scheduling
• Maximum Sum of Non-Adjacent Elements

🔹 Template:

int solve(int i, int prevIndex, int[] nums) {
    if (i == nums.length) return 0;

    // Not take
    int notTake = solve(i + 1, prevIndex, nums);

    // Take
    int take = 0;
    if (prevIndex == -1 || nums[i] > nums[prevIndex])
        take = 1 + solve(i + 1, i, nums);

    return Math.max(take, notTake);
}

---

5️⃣ Partition DP

Split array into segments (e.g., Palindrome Partition, Burst Balloons).

🔹 Problem Types:

• Palindrome Partitioning II
• Matrix Chain Multiplication
• Burst Balloons

🔹 Template:

int solve(int i, int j, int[] arr) {
    if (i >= j) return 0;

    int minCost = Integer.MAX_VALUE;

    for (int k = i; k < j; k++) {
        int cost = solve(i, k, arr) + solve(k + 1, j, arr) + costFunction(i, k, j);
        minCost = Math.min(minCost, cost);
    }

    return minCost;
}

---

6️⃣ Decision Tree / Backtracking

Explore all paths — often exponential, but needed for enumeration problems.

🔹 Problem Types:

• Generate Subsequences
• Combinations / Permutations
• N-Queens
• Word Search

🔹 Template:

void backtrack(int i, List<Integer> path, int[] nums) {
    if (i == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }

    // Take
    path.add(nums[i]);
    backtrack(i + 1, path, nums);
    path.remove(path.size() - 1);

    // Not take
    backtrack(i + 1, path, nums);
}

---

7️⃣ Grid DP

Grid traversal problems with movement in directions.

🔹 Problem Types:

• Unique Paths / Obstacles
• Minimum Path Sum
• Grid Cost Problems

🔹 Template:

int solve(int i, int j, int[][] grid) {
    if (i >= m || j >= n) return INF;
    if (i == m - 1 && j == n - 1) return grid[i][j];

    return grid[i][j] + Math.min(
        solve(i + 1, j, grid),
        solve(i, j + 1, grid)
    );
}

---

8️⃣ Digit DP

Special type of DP on digits of a number with constraints (e.g., "count numbers with X property").

🔹 Problem Types:

• Count Numbers <= N with some digit rules
• Sum of Digits in range
• Bounded digit DP

🔹 Template:

int solve(int pos, boolean tight, boolean leadingZero, String num) {
    if (pos == num.length()) return base_case;

    int limit = tight ? num.charAt(pos) - '0' : 9;
    int res = 0;

    for (int d = 0; d <= limit; d++) {
        res += solve(pos + 1,
                     tight && (d == limit),
                     leadingZero && (d == 0),
                     num);
    }

    return res;
}

---

9️⃣ Bitmask DP

Useful when tracking subset combinations efficiently with bitmasking.

🔹 Problem Types:

• Traveling Salesman Problem (TSP)
• Assignment Problems
• Max Score Assignments

🔹 Template:

int solve(int mask, int pos, int[][] cost) {
    if (mask == allVisitedMask) return 0;

    if (dp[mask][pos] != -1) return dp[mask][pos];

    int ans = Integer.MAX_VALUE;

    for (int city = 0; city < n; city++) {
        if ((mask & (1 << city)) == 0) {
            ans = Math.min(ans, cost[pos][city] + solve(mask | (1 << city), city, cost));
        }
    }

    return dp[mask][pos] = ans;
}

---

🔟 Memoization and Tabulation Conversions

• Memoization → Top-down recursion with dp[] array or map.
• Tabulation → Bottom-up DP using dp[] arrays with for-loops.
• Space Optimization → Compress 2D dp[i][j] into 1D prev[] and curr[] if dependencies allow.

---

📦 Final Tips

Pattern	Look For
Take / Not Take	Subset, inclusion-exclusion
Unbounded	Reuse of elements allowed
Subsequences	Comparing two sequences
Partition DP	Problem splits at a point
Backtracking	Enumerate all combinations
Grid DP	Movement in a matrix
Bitmask DP	State of "used/not used"
Digit DP	Number digit constraints
Game DP	Two players, optimal strategy