Finding Minimum Answers using Dynamic Programming

When the recurrence uses min instead of max—shortest paths on implicit graphs, minimum cost to reach a state—the mechanics match maximization but initialize with infinity carefully.

Why this shows up in the real world

Supply chain minimizes delay; compiler instruction scheduling minimizes stalls.

Core idea (explained for students)

Use dp[x] = min(dp[x], dp[prev]+cost); for unreachable use a large sentinel smaller than overflow-prone sums.

Try this in Python

def min_path_sum(grid: list[list[int]]) -> int:
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    dp = [[10**18] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            best = 10**18
            if i:
                best = min(best, dp[i - 1][j])
            if j:
                best = min(best, dp[i][j - 1])
            dp[i][j] = best + grid[i][j]
    return dp[-1][-1]


print(min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))

Common mistakes

• Using 0 as unreachable instead of inf—min absorbs bad values.
• Mixing max and min in the same table accidentally.

Key takeaways

• Explicit infinities per problem bounds.
• Unit-test transitions that should be inactive.