DP on Grids

Key Signals & Indicators

• Input is a 2D matrix or grid layout
• Finding paths or optimization metrics from source to destination (e.g. min path sum)
• Allowed directions are constrained (e.g. only down and right)

// C++ DP on Grids Template
#include <vector>
#include <algorithm>

int minPathSumGrid(const std::vector<std::vector<int>>& grid) {
    if (grid.empty()) return 0;
    int rows = grid.size();
    int cols = grid[0].size();
    
    std::vector<std::vector<int>> dp(rows, std::vector<int>(cols, 0));
    dp[0][0] = grid[0][0];
    
    // Fill first row
    for (int c = 1; c < cols; ++c) dp[0][c] = dp[0][c - 1] + grid[0][c];
    // Fill first col
    for (int r = 1; r < rows; ++r) dp[r][0] = dp[r - 1][0] + grid[r][0];
    
    // Fill the rest of the grid
    for (int r = 1; r < rows; ++r) {
        for (int c = 1; c < cols; ++c) {
            dp[r][c] = grid[r][c] + std::min(dp[r - 1][c], dp[r][c - 1]);
        }
    }
    return dp[rows - 1][cols - 1];
}