Pattern visualizer
Minimum Path Sum
A cell can only be entered from directly above or directly to its left — those are the only two moves allowed. So the cheapest way to reach any cell is its own cost plus whichever of those two neighbors was cheaper to reach. The top row and left column each have only one possible predecessor, so they fill in as running sums; every interior cell then picks the smaller of its two already-known neighbors. Animated on: grid = [[1,3,1],[1,5,1],[4,2,1]] — moving only right or down from top-left, find the path to bottom-right that minimizes the sum of the numbers it passes through..
dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]) — only right/down moves reach a cell
A 3x3 grid of costs. Only right and down moves are allowed, so every cell is reached from exactly one of two neighbors — the cell above or the cell to its left.
1FUNCTION minPathSum(grid):2 dp[0][0] <- grid[0][0]3 FOR c FROM 1 TO n-1:4 dp[0][c] <- dp[0][c-1] + grid[0][c]5 FOR r FROM 1 TO m-1:6 dp[r][0] <- dp[r-1][0] + grid[r][0]7 FOR r FROM 1 TO m-1:8 FOR c FROM 1 TO n-1:9 dp[r][c] <- grid[r][c] + MIN(dp[r-1][c], dp[r][c-1])10 RETURN dp[m-1][n-1]
← / → step · space play · Home restart