Grid DP / Pathfinding Template

Use when navigating a 2D grid with movement constraints.

🔹 Problem Types:

Unique Paths / Minimum Path Sum
Grid with Obstacles
Max Gold Collection
Longest Increasing Path
Robot Paths

🔹 Template (Bottom-Up):

int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];

    dp[0][0] = grid[0][0];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m - 1][n - 1];
}

🧠 Optimization:

Use 1D array when only i-1 and i rows are needed.

5️⃣ Partition DP (Interval DP)

Used when a problem requires breaking an array into segments and combining results.

🔹 Problem Types:

Matrix Chain Multiplication
Burst Balloons
Palindrome Partitioning (Min cuts)
Boolean Parenthesization

🔹 Template:

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

    if (dp[i][j] != -1) return dp[i][j];

    int min = Integer.MAX_VALUE;
    for (int k = i; k < j; k++) {
        int cost = solve(i, k, arr) + solve(k + 1, j, arr) + arr[i - 1] * arr[k] * arr[j];
        min = Math.min(min, cost);
    }

    return dp[i][j] = min;
}

6️⃣ Bitmask DP

Efficient way to track and memoize over subsets (2^n states). Core to scheduling, assignments, and optimization over combinations.

🔹 Problem Types:

Traveling Salesman Problem (TSP)
Job Scheduling / Assignment
Count of Subsets with Constraints
Max Compatibility Score

🔹 Template:

int tsp(int mask, int pos, int[][] dist) {
    if (mask == (1 << n) - 1) return dist[pos][0];

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

    int minCost = Integer.MAX_VALUE;
    for (int city = 0; city < n; city++) {
        if ((mask & (1 << city)) == 0) {
            int newCost = dist[pos][city] + tsp(mask | (1 << city), city, dist);
            minCost = Math.min(minCost, newCost);
        }
    }

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

7️⃣ Digit DP

Specialized DP used in number-based constraints where you have to count numbers in a range satisfying digit-level properties.

🔹 Problem Types:

Count numbers <= N with digit sum or no adjacent repeats
Count numbers with restricted digits
Count valid phone numbers, number of beautiful integers

🔹 Template:

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

    if (dp[pos][sum][tight ? 1 : 0] != -1)
        return dp[pos][sum][tight ? 1 : 0];

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

    for (int digit = 0; digit <= limit; digit++) {
        ans += solve(
            pos + 1,
            sum + digit,
            tight && (digit == limit),
            num
        );
    }

    return dp[pos][sum][tight ? 1 : 0] = ans;
}

🧩 Summary Table: Master Templates by Problem Class

Template Type	Solves Problems Like	Key Feature
Backtracking	Generate/Enumerate paths	DFS + undo
Take/Not-Take DP	Subsets, knapsack	Binary choice per element
DP on Strings	LCS, Edit Distance, Matching	2D DP on sequence indices
Grid DP	Matrix traversal problems	2D DP with movement
Partition DP	Segment combinations	Interval partitioning
Bitmask DP	TSP, Subset Optimization	State = bitmask
Digit DP	Counting valid numbers	DP by digit position