Pattern visualizer
Number of Ways to Reach Destination (DP on Grid)
A cell can only be entered from directly above or directly to its left — those are the only two moves allowed. Every path that reaches either neighbor extends into a distinct path through this cell, so the count here is just the sum of the counts at those two neighbors. The top row and left column each have only one possible route in, so they start at 1 and every interior cell builds on already-known neighbors. Animated on: m = 3, n = 3 — a robot starts top-left and can only move down or right; count the distinct paths to the bottom-right corner..
dp[r][c] = dp[r-1][c] + dp[r][c-1]
dp[r][c] = dp[r-1][c] + dp[r][c-1] — paths arrive only from above or from the left
A 3x3 grid. The robot only ever moves down or right, so the number of ways to reach a cell is the sum of the ways to reach the cell above it and the cell to its left.
1FUNCTION countPaths(m, n):2 dp[0][0] <- 13 FOR c FROM 1 TO n-1:4 dp[0][c] <- dp[0][c-1]5 FOR r FROM 1 TO m-1:6 dp[r][0] <- dp[r-1][0]7 FOR r FROM 1 TO m-1:8 FOR c FROM 1 TO n-1:9 dp[r][c] <- dp[r-1][c] + dp[r][c-1]10 RETURN dp[m-1][n-1]
← / → step · space play · Home restart