LeetCode 64 — Minimum Path Sum (C++ DP + Memoization)

Written by Shivam Kachhadiya • Last Updated: Feb 16, 2026

Classic Dynamic Programming grid problem. We must move from top-left to bottom-right minimizing total cost.

Problem Statement

Given an m × n grid filled with non-negative numbers, find a path which minimizes the sum. Moves allowed → Right or Down only.

Handwritten Notes

Intuition

• Each cell comes from top or left
• Choose minimum
• Store results using memoization

C++ Code (Memoization)

class Solution {
public:
    int solve(vector>& grid, int i, int j,
              vector>& dp) {

        if (i < 0 || j < 0) return 1e9;
        if (i == 0 && j == 0) return grid[0][0];

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

        int top  = grid[i][j] + solve(grid, i-1, j, dp);
        int left = grid[i][j] + solve(grid, i, j-1, dp);

        return dp[i][j] = min(top, left);
    }

    int minPathSum(vector>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector> dp(m, vector(n, -1));
        return solve(grid, m-1, n-1, dp);
    }
};