Unique Paths and Minimum Path Sum on Grids
Fill a 2D DP table for unique paths with and without obstacles, then adapt it to minimise the sum of values along a path.
Unique Paths and Minimum Path Sum on Grids is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Unique Paths on a Grid
Unique Paths (LeetCode 62) asks: in an m×n grid, how many distinct paths go from the top-left corner to the bottom-right corner if you can only move right or down? For a 3×7 grid the answer is 28. The key insight is that every path to cell (i,j) must come from either (i-1,j) (above) or (i,j-1) (left), giving a natural 2D DP formulation.
# 3x7 grid: robot starts at (0,0), goes to (2,6)
# Must make exactly 2 down-moves and 6 right-moves
# Total moves = 8, choose 2 for down = C(8,2) = 28
import math
print('Unique paths 3x7:', math.comb(3+7-2, 3-1)) # 28
print('Unique paths 3x3:', math.comb(3+3-2, 3-1)) # 6
print('Unique paths 2x2:', math.comb(2+2-2, 2-1)) # 22D DP Table for Unique Paths
Define dp[i][j] = number of paths to cell (i,j). The first row and first column are all 1s (only one way to reach any cell in the top row or leftmost column). For other cells: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Fill the table row by row and the answer is dp[m-1][n-1]. Time complexity: O(m×n), space: O(m×n) reducible to O(n).
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
# First row and column stay as 1s (base cases)
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 3)) # 6
print(unique_paths(1, 1)) # 1 (already at destination)Space Optimisation to O(n)
Since dp[i][j] depends only on the current row and the previous row, you can replace the full 2D table with a single 1D array. Initialise all values to 1, then for each row, update in place: dp[j] += dp[j-1]. After processing row i, dp[j] holds the value that was dp[i][j] in the 2D table. This is a common optimisation pattern for 2D DP problems.
def unique_paths_1d(m, n):
dp = [1] * n # initial row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # dp[j] was dp[i-1][j], dp[j-1] is dp[i][j-1]
return dp[n-1]
print(unique_paths_1d(3, 7)) # 28
print(unique_paths_1d(3, 3)) # 6
# Or use math for O(1)
import math
print(math.comb(3+7-2, 3-1)) # 28Unique Paths II: Obstacles
Unique Paths II (LeetCode 63) adds obstacles (cells marked 1) to the grid. Any path through an obstacle is invalid, so dp[i][j] = 0 if obstacle[i][j] == 1. Otherwise, the recurrence is the same: dp[i][j] = dp[i-1][j] + dp[i][j-1]. The start or end being blocked immediately gives 0. Initialise base cases carefully — once a 1 appears in the first row or column, all subsequent cells in that row/column are 0.
def unique_paths_with_obstacles(obstacle_grid):
m, n = len(obstacle_grid), len(obstacle_grid[0])
dp = [[0] * n for _ in range(m)]
# First row
for j in range(n):
if obstacle_grid[0][j] == 1: break
dp[0][j] = 1
# First column
for i in range(m):
if obstacle_grid[i][0] == 1: break
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
if obstacle_grid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
grid = [[0,0,0],[0,1,0],[0,0,0]]
print(unique_paths_with_obstacles(grid)) # 2Minimum Path Sum Problem
Minimum Path Sum (LeetCode 64) asks: given an m×n grid filled with non-negative integers, find the path from top-left to bottom-right that minimises the sum of all numbers along the path (moving only right or down). For example, in [[1,3,1],[1,5,1],[4,2,1]], the path 1→3→1→1→1 gives sum 7. The DP state is the same as unique paths, but the recurrence now uses minimum instead of addition.
grid = [[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
# Optimal path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
# Values: 1 + 3 + 1 + 1 + 1 = 7
print('Expected minimum path sum:', 7)Min Path Sum DP Implementation
Define dp[i][j] = minimum cost to reach cell (i,j). Base case: dp[0][0] = grid[0][0]. First row: dp[0][j] = dp[0][j-1] + grid[0][j] (only way to come from left). First column: dp[i][0] = dp[i-1][0] + grid[i][0] (only way to come from above). General: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). This is a direct translation of the optimality principle.
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0]
for j in range(1, n): # first row
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m): # first column
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7In-Place Min Path Sum
If you are allowed to modify the input grid, you can update it in place to avoid allocating a separate DP table. This reduces space to O(1) auxiliary (beyond the input). Interviewers sometimes ask about this optimisation — clarify whether modifying the input is allowed before doing so. If not, the 1D rolling array trick gives O(n) space without modifying input.
def min_path_sum_inplace(grid):
m, n = len(grid), len(grid[0])
# Mutate in place
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
if i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Triangle Minimum Path Sum
Triangle (LeetCode 120) asks for the minimum path sum from top to bottom in a triangle array, where each step goes to an adjacent number in the row below. Bottom-up DP is cleanest: start from the second-to-last row and for each cell, add the minimum of the two cells directly below. This avoids tracking starting indices and naturally bubbles the answer up to the apex.
def minimum_total(triangle):
# Bottom-up: start from second-to-last row
dp = triangle[-1][:] # copy of bottom row
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
dp[col] = triangle[row][col] + min(dp[col], dp[col+1])
return dp[0]
triangle = [
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
print(minimum_total(triangle)) # 11 (2+3+5+1)Grid DP on a Dungeon
Dungeon Game (LeetCode 174) asks for the minimum initial health to rescue a princess in the bottom-right corner of a grid with negative (damage) and positive (heal) cells. You must go right or down. The trick is to fill the DP table backwards (from bottom-right to top-left), computing the minimum health needed at each cell. At each cell: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Health must always stay at least 1.
def calculate_minimum_hp(dungeon):
m, n = len(dungeon), len(dungeon[0])
dp = [[0]*n for _ in range(m)]
# Fill from bottom-right
dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
for i in range(m-2, -1, -1): # last column
dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
for j in range(n-2, -1, -1): # last row
dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
need = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(1, need - dungeon[i][j])
return dp[0][0]
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
print(calculate_minimum_hp(dungeon)) # 7Comparing Grid DP Problems
Grid DP problems share the same structure but differ in direction of fill and transition operation: Unique Paths uses addition (count all ways). Min Path Sum uses minimum (optimise). Dungeon Game fills backwards (health needed from the future). When approaching a new grid DP, ask yourself: (1) What does each cell represent? (2) Which direction do I fill? (3) What operation combines the neighbours? Answering these three questions reveals the full solution.
# Summary: Grid DP Patterns
#
# Problem Fill Dir Transition
# Unique Paths top-left dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Unique Paths II top-left same but 0 if obstacle
# Min Path Sum top-left dp[i][j] = grid[i][j] + min(above, left)
# Triangle bottom-up dp[col] = row[col] + min(dp[col], dp[col+1])
# Dungeon bottom-right max(1, min(right, down) - cell)
# Recognise the pattern, write the transition, verify with examples
print('Grid DP summary complete')Complexity Summary for Grid DP
All grid DP problems here run in O(m×n) time. Space ranges from O(m×n) for a full table down to O(n) with a 1D rolling array and O(1) auxiliary when the grid can be modified in place. In interviews, mention the O(n) space optimisation after presenting the O(m×n) solution — it demonstrates awareness of trade-offs. For all problems, also consider whether a greedy shortcut exists (like the math formula for unique paths).
# O(n) space version of Min Path Sum
def min_path_sum_1d(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
dp[0] += grid[i][0] # first column: only from above
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
return dp[n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_1d(grid)) # 7Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Unique Paths fills a 2D table with dp[i][j] = dp[i-1][j] + dp[i][j-1] and can be computed in O(1) with combinatorics, Min Path Sum uses the same structure but replaces addition with min for optimal path cost, and all grid DP problems share the pattern of defining a state per cell and choosing a transition operator (sum, min, max). Next up we explore the Longest Common Subsequence using 2D DP on two sequences.
Frequently asked questions
Is the “Unique Paths and Minimum Path Sum on Grids” lesson free?
Yes — the full text of “Unique Paths and Minimum Path Sum on Grids” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Unique Paths and Minimum Path Sum on Grids”?
Fill a 2D DP table for unique paths with and without obstacles, then adapt it to minimise the sum of values along a path. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Unique Paths and Minimum Path Sum on Grids” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Unique Paths and Minimum Path Sum on Grids
- Longest Common Subsequence
- Edit Distance (Levenshtein)
- Space Optimisation for 2D DP