Minimum Path Sum

Problem

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.

Examples

The brute-force approach

Recursively try all paths (right and down). Return the minimum sum path from (0,0) to (m-1,n-1).

def min_path(r, c):
    if r == m-1 and c == n-1: return grid[r][c]
    if r == m-1: return grid[r][c] + min_path(r, c+1)
    if c == n-1: return grid[r][c] + min_path(r+1, c)
    return grid[r][c] + min(min_path(r+1,c), min_path(r,c+1))

O(2^(m+n)) — exponential without memoization.

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

At cell (i,j), you can arrive from above (i-1,j) or from the left (i,j-1). Why do you take the minimum of those two, not the maximum?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.