Definition
- Unique Paths – a grid DP problem where
dp[i][j]counts the number of distinct paths from the top-left to cell(i, j)when only rightward and downward moves are allowed. - Base cases – the entire first row and first column are all 1, because along an edge there is exactly one straight path.
- Recurrence –
dp[i][j] = dp[i-1][j] + dp[i][j-1], summing paths from above and from the left. - Space optimisation – a single rolling row of size n, updated left to right, replaces the full grid.
- Closed form – the binomial coefficient C(m+n-2, m-1) gives the answer in O(m+n) time.
At the National Bank of India, a sealed document must be routed across a grid of branch offices, moving only east or south. The number of distinct routes to any office is the sum of routes to the office to its west and the office to its north.
Understanding the Concepts
What is the Unique Paths problem?
A robot starts at the top-left corner of an m-by-n grid and can only move right or down at each step. Count the number of distinct paths from the top-left to the bottom-right. This is a classic grid dynamic programming problem.
package com.bank.service;
public class UniquePaths {
public int countPaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
Why are the base cases all 1?
Along the top row, the robot can only move right, so there is exactly one path to every cell in that row. Along the left column, the robot can only move down, so there is exactly one path to every cell in that column. These are the base cases that seed the DP.
package com.bank.service;
public class BaseCaseDemo {
public static void main(String[] args) {
int m = 3, n = 4;
int[][] dp = new int[m][n];
// First column: only one path (all down)
for (int i = 0; i < m; i++) dp[i][0] = 1;
// First row: only one path (all right)
for (int j = 0; j < n; j++) dp[0][j] = 1;
System.out.println("First row: "
+ java.util.Arrays.toString(dp[0]));
System.out.println("First col: "
+ dp[0][0] + ", " + dp[1][0] + ", " + dp[2][0]);
}
}
First row: [1, 1, 1, 1]
First col: 1, 1, 1
How does the recurrence work?
Each interior cell can only be reached from directly above (the cell in the previous row) or directly to the left (the cell in the previous column). These two sets of paths are completely disjoint, so the total paths to a cell is their sum.
package com.bank.service;
public class RecurrenceTrace {
public static void main(String[] args) {
int m = 3, n = 3;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
System.out.println("dp[" + i + "][" + j + "] = "
+ dp[i - 1][j] + " + " + dp[i][j - 1]
+ " = " + dp[i][j]);
}
}
// dp[2][2] = 6
}
}
dp[1][1] = 1 + 1 = 2
dp[1][2] = 1 + 2 = 3
dp[2][1] = 2 + 1 = 3
dp[2][2] = 3 + 3 = 6
How does the single-row space optimisation work?
Since each row depends only on the row above and the cell to the left, we can collapse the grid to a single array. Before updating, dp[j] holds the value from the row above; after adding dp[j-1], it holds the value from the left. We update left to right.
package com.bank.service;
public class UniquePathsOptimized {
public int countPaths(int m, int n) {
int[] dp = new int[n];
java.util.Arrays.fill(dp, 1); // first row: all 1
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1]; // dp[j] (above) + dp[j-1] (left)
}
}
return dp[n - 1];
}
public static void main(String[] args) {
System.out.println("3x7 grid: "
+ new UniquePathsOptimized().countPaths(3, 7)); // 28
}
}
3x7 grid: 28
What is the combinatorial closed-form solution?
Every path consists of exactly (m-1) down moves and (n-1) right moves, for a total of (m+n-2) moves. The answer is the number of ways to choose which moves are down: C(m+n-2, m-1). This runs in O(m+n) time but can overflow for large grids.
package com.bank.service;
public class UniquePathsCombinatorial {
public long countPaths(int m, int n) {
// C(m+n-2, m-1)
long result = 1;
for (int i = 1; i < m; i++) {
result = result * (n - 1 + i) / i;
}
return result;
}
public static void main(String[] args) {
System.out.println("3x7 grid: "
+ new UniquePathsCombinatorial().countPaths(3, 7)); // 28
System.out.println("10x10 grid: "
+ new UniquePathsCombinatorial().countPaths(10, 10)); // 48620
}
}
3x7 grid: 28
10x10 grid: 48620
What are the edge cases?
Edge cases include a 1x1 grid (one path: stay in place), a 1xN or Mx1 grid (one path: all right or all down), and very large grids where the combinatorial formula risks overflow.
package com.bank.service;
public class PathEdgeCases {
public static void main(String[] args) {
UniquePathsOptimized solver = new UniquePathsOptimized();
System.out.println("1x1: " + solver.countPaths(1, 1)); // 1
System.out.println("1x5: " + solver.countPaths(1, 5)); // 1
System.out.println("5x1: " + solver.countPaths(5, 1)); // 1
System.out.println("2x2: " + solver.countPaths(2, 2)); // 2
System.out.println("3x3: " + solver.countPaths(3, 3)); // 6
}
}
1x1: 1
1x5: 1
5x1: 1
2x2: 2
3x3: 6
How is this different from Unique Paths II (with obstacles)?
Unique Paths II adds blocked cells that the robot cannot pass through. For blocked cells, dp[i][j] = 0. For unblocked cells, the recurrence is the same. The combinatorial shortcut no longer applies because obstacles break the uniform structure.
| Aspect | Unique Paths I | Unique Paths II |
|---|---|---|
| Obstacles | None | Some cells blocked |
| Blocked cell | N/A | dp[i][j] = 0 |
| Combinatorial | C(m+n-2, m-1) | Not applicable |
| Time | O(m*n) or O(m+n) | O(m*n) only |
// Unique Paths II: handle obstacles
if (grid[i][j] == 1) {
dp[i][j] = 0; // blocked
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-1]; // same recurrence
}
How would you apply this in a banking system?
At the National Bank of India, a loan approval workflow is modeled as a grid where a request moves either to the next approval stage (down) or across to the next department (right). Risk analysts count the number of distinct approval routes from intake to final sign-off.
package com.bank.service;
public class ApprovalRouteCounter {
public int countApprovalRoutes(int stages, int departments) {
int[] dp = new int[departments];
java.util.Arrays.fill(dp, 1);
for (int i = 1; i < stages; i++) {
for (int j = 1; j < departments; j++) {
dp[j] += dp[j - 1];
}
}
return dp[departments - 1];
}
public static void main(String[] args) {
ApprovalRouteCounter counter = new ApprovalRouteCounter();
System.out.println("4 stages, 5 departments: "
+ counter.countApprovalRoutes(4, 5)); // 35
}
}
4 stages, 5 departments: 35
What should a senior engineer know?
A senior engineer should know all three approaches (full grid DP, single-row DP, combinatorial formula) and when to use each. The full grid is simplest to implement. The single-row saves memory. The combinatorial formula is fastest but risks overflow and does not work with obstacles. They should also recognize this as Pascal's Triangle rotated.
// The DP grid is equivalent to Pascal's Triangle:
// dp[i][j] = C(i+j, i)
//
// 1 1 1 1
// 1 2 3 4
// 1 3 6 10
//
// Each cell is a binomial coefficient.
Visual Overview
3x4 Grid DP:
col 0 col 1 col 2 col 3
┌───────┬───────┬───────┬───────┐
row 0│ 1 │ 1 │ 1 │ 1 │ ← base: all 1
├───────┼───────┼───────┼───────┤
row 1│ 1 │ 2 │ 3 │ 4 │
├───────┼───────┼───────┼───────┤
row 2│ 1 │ 3 │ 6 │ 10 │ ← answer
└───────┴───────┴───────┴───────┘
↑ base ↑
all 1 dp[2][3]=10
Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[2][3] = dp[1][3] + dp[2][2] = 4 + 6 = 10
Single-row optimization:
Row 0: [1, 1, 1, 1]
Row 1: [1, 2, 3, 4] (dp[j] += dp[j-1])
Row 2: [1, 3, 6, 10] (dp[j] += dp[j-1])
Answer: dp[3] = 10
Key Takeaway
Unique Paths is a grid dynamic programming problem. I define dp[i][j] as the number of distinct paths from the top-left to cell (i, j), given that the robot moves only right or down. The base cases are the entire first row and first column, all ones, because along an edge there is exactly one straight path.
For every interior cell, the robot arrives from directly above or directly from the left, so the number of paths is the sum of the paths to those two neighbors. The answer is the bottom-right cell. I reduce memory to a single rolling row because each row depends only on the one above it, and there is also a closed-form combinatorial answer as C(m+n-2, m-1).
Edge cases include 1x1, 1xN, and Mx1 grids (all have exactly one path), and very large grids where the combinatorial formula risks overflow. The DP grid is equivalent to Pascal's Triangle, where each cell is a binomial coefficient.
At the National Bank of India, I modeled a loan approval workflow as a grid where a request moved to the next approval stage or across to the next department. The single-row DP counted the distinct approval routes from intake to final sign-off efficiently.
Remember one sentence: paths to a cell equal paths from above plus paths from the left, with edges all one.
---