This content originally appeared on DEV Community and was authored by DevCorner2

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

🛠 Want More?

Other advanced templates I can deliver upon request:

• Monotonic Stack (largest rectangle, next greater)
• DP + Binary Search (LIS in O(n log n), Min cost to achieve condition)
• 2D Range DP (Egg Drop, Maximum Submatrix Sum)
• Rolling Hash + DP (String compression / repetition)
• Graph DP (Tree DP / DP on DAGs)

This content originally appeared on DEV Community and was authored by DevCorner2

Print Share Comment Cite Upload Translate Updates

APA

DevCorner2 | Sciencx (2025-07-29T05:39:41+00:00) Grid DP / Pathfinding Template. Retrieved from https://www.scien.cx/2025/07/29/grid-dp-pathfinding-template/

MLA

" » Grid DP / Pathfinding Template." DevCorner2 | Sciencx - Tuesday July 29, 2025, https://www.scien.cx/2025/07/29/grid-dp-pathfinding-template/

HARVARD

DevCorner2 | Sciencx Tuesday July 29, 2025 » Grid DP / Pathfinding Template., viewed ,<https://www.scien.cx/2025/07/29/grid-dp-pathfinding-template/>

VANCOUVER

DevCorner2 | Sciencx - » Grid DP / Pathfinding Template. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2025/07/29/grid-dp-pathfinding-template/

CHICAGO

" » Grid DP / Pathfinding Template." DevCorner2 | Sciencx - Accessed . https://www.scien.cx/2025/07/29/grid-dp-pathfinding-template/

IEEE

" » Grid DP / Pathfinding Template." DevCorner2 | Sciencx [Online]. Available: https://www.scien.cx/2025/07/29/grid-dp-pathfinding-template/. [Accessed: ]

rf:citation

» Grid DP / Pathfinding Template | DevCorner2 | Sciencx | https://www.scien.cx/2025/07/29/grid-dp-pathfinding-template/ |

Please log in to upload a file.

There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.