Definition
- Unique Paths – count routes from top-left to bottom-right of a grid when only right and down moves are allowed.
- Recurrence –
dp[i][j] = dp[i-1][j] + dp[i][j-1], summing arrivals from above and from the left. - Base cases – top row and left column are all 1 because an edge has exactly one straight path.
- Space optimisation – a single row updated left to right reduces space to O(n).
- Closed form – the binomial coefficient C(m+n-2, m-1) computes the answer in O(m+n).
The National Bank of India models an approval workflow as a grid where a request moves to the next stage (down) or the next department (right). The number of distinct approval routes from intake to final sign-off is the grid path count.
Understanding the Concepts
What is the Unique Paths problem?
Count the distinct paths from the top-left to the bottom-right of an m-by-n grid, moving only right or down at each step. This is a foundational grid DP problem that teaches recurrence derivation and space optimisation.
package com.bank.service;
public class UniquePathsDP {
public int countPaths(int m, int n) {
int[] dp = new int[n];
java.util.Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
}
How do you derive the recurrence?
The robot can only arrive at cell (i, j) from the cell directly above (i-1, j) or the cell directly to the left (i, j-1). Since these two sets of incoming paths are completely disjoint, the total is their sum: dp[i][j] = dp[i-1][j] + dp[i][j-1].
package com.bank.service;
public class RecurrenceDerivation {
public static void main(String[] args) {
int m = 3, n = 4;
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("Grid:");
for (int[] row : dp)
System.out.println(java.util.Arrays.toString(row));
}
}
Grid:
[1, 1, 1, 1]
[1, 2, 3, 4]
[1, 3, 6, 10]
How does the single-row optimisation work?
Each row depends only on the previous row and the cell to the left. A single array of size n suffices. Before updating, dp[j] holds the above-cell value from the previous row; dp[j-1] was already updated in this row and holds the left-cell value. Adding them updates dp[j] in place.
package com.bank.service;
public class SingleRowTrace {
public static void main(String[] args) {
int m = 3, n = 7;
int[] dp = new int[n];
java.util.Arrays.fill(dp, 1);
System.out.println("Row 0: " + java.util.Arrays.toString(dp));
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) dp[j] += dp[j - 1];
System.out.println("Row " + i + ": "
+ java.util.Arrays.toString(dp));
}
System.out.println("Answer: " + dp[n - 1]); // 28
}
}
Row 0: [1, 1, 1, 1, 1, 1, 1]
Row 1: [1, 2, 3, 4, 5, 6, 7]
Row 2: [1, 3, 6, 10, 15, 21, 28]
Answer: 28
What is the combinatorial closed-form solution?
Every path is a sequence of exactly (m-1) down moves and (n-1) right moves, for a total of (m+n-2) moves. Choosing which moves are down gives C(m+n-2, m-1). This formula computes the answer in O(min(m, n)) time without building a grid.
package com.bank.service;
public class CombinatorialPaths {
public long countPaths(int m, int n) {
long result = 1;
for (int i = 1; i < m; i++) {
result = result * (n - 1 + i) / i;
}
return result;
}
public static void main(String[] args) {
CombinatorialPaths cp = new CombinatorialPaths();
System.out.println("3x7: " + cp.countPaths(3, 7)); // 28
System.out.println("10x10: " + cp.countPaths(10, 10)); // 48620
}
}
3x7: 28
10x10: 48620
How is this related to Pascal's Triangle?
The filled DP grid is a rotated Pascal's Triangle. Each cell dp[i][j] equals the binomial coefficient C(i+j, i). This connection provides mathematical insight: the grid of path counts has exactly the same structure as binomial coefficients.
// Pascal's Triangle connection:
//
// dp[0][0]=C(0,0)=1 dp[0][1]=C(1,0)=1 dp[0][2]=C(2,0)=1
// dp[1][0]=C(1,1)=1 dp[1][1]=C(2,1)=2 dp[1][2]=C(3,1)=3
// dp[2][0]=C(2,2)=1 dp[2][1]=C(3,2)=3 dp[2][2]=C(4,2)=6
//
// Each cell: C(i+j, i) = C(i+j, j)
What are the edge cases?
A 1x1 grid has one path (start equals end). A 1xN or Mx1 grid has exactly one path (all right or all down). Very large grids may overflow int in the combinatorial formula.
package com.bank.service;
public class PathEdgeCases2 {
public static void main(String[] args) {
UniquePathsDP solver = new UniquePathsDP();
System.out.println("1x1: " + solver.countPaths(1, 1)); // 1
System.out.println("1x10: " + solver.countPaths(1, 10)); // 1
System.out.println("2x2: " + solver.countPaths(2, 2)); // 2
System.out.println("4x4: " + solver.countPaths(4, 4)); // 20
}
}
1x1: 1
1x10: 1
2x2: 2
4x4: 20
What are common mistakes?
The most common mistake is initialising the first row or column to 0 instead of 1, which zeros out the entire grid. Another mistake is updating the rolling row right-to-left instead of left-to-right, which uses the wrong left-neighbor value.
// WRONG: first row initialized to 0
int[] dp = new int[n]; // all 0 by default
// dp[j] += dp[j-1] starts from 0, everything stays 0!
// CORRECT: fill with 1
int[] dp = new int[n];
java.util.Arrays.fill(dp, 1);
How would you apply this in a banking system?
At the National Bank of India, a loan approval workflow moves through stages (rows) and departments (columns). Risk analysts count the distinct approval routes to understand the process complexity.
package com.bank.service;
public class WorkflowRouteAnalyzer {
public int countRoutes(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) {
WorkflowRouteAnalyzer analyzer = new WorkflowRouteAnalyzer();
System.out.println("5 stages, 4 depts: "
+ analyzer.countRoutes(5, 4)); // 35
}
}
5 stages, 4 depts: 35
What should a senior engineer know?
A senior engineer should know all three approaches and their trade-offs. The full grid DP is simplest. The single-row saves memory to O(n). The combinatorial formula is fastest at O(min(m,n)) but risks overflow and does not extend to obstacle variants. They should also recognise the Pascal's Triangle connection.
// Approach comparison:
// 1. Full grid DP: O(m*n) time, O(m*n) space - simplest
// 2. Single-row DP: O(m*n) time, O(n) space - practical
// 3. Combinatorial: O(min(m,n)) time, O(1) space - fastest
// (but risks overflow, no obstacle support)
Visual Overview
3x7 Grid (single-row DP):
Initialize: [1, 1, 1, 1, 1, 1, 1]
Row 1: dp[j] += dp[j-1]
[1, 2, 3, 4, 5, 6, 7]
Row 2: dp[j] += dp[j-1]
[1, 3, 6, 10, 15, 21, 28]
↑
Answer = 28
Combinatorial:
Total moves = (3-1) + (7-1) = 8
Down moves = 2
C(8, 2) = 8! / (2! * 6!) = 28
Path = sequence of R and D:
R R R R R R D D (one arrangement)
Choose 2 positions for D out of 8 total = C(8,2) = 28
Key Takeaway
Unique Paths counts the routes across a grid when only rightward and downward moves are allowed. The recurrence falls directly from the movement rule: any cell can only be entered from above or from the left, so the path count is their sum. The entire top row and left column have exactly one path each, seeding the base cases.
I collapse the grid to a single row initialised to all ones and update left to right. In that row, the value already sitting in a cell represents the above count, and the value just to its left represents the left count, so a single addition does the work. This runs in O(m * n) time and O(n) space.
The closed-form binomial coefficient C(m+n-2, m-1) gives the answer in O(min(m, n)) time, but it risks overflow for large grids and does not extend to obstacle variants. A senior engineer knows all three approaches and when to use each.
At the National Bank of India, I used this to model a loan approval workflow as a grid, counting the distinct routes from intake to final sign-off. The single-row DP was practical for the grid sizes involved.
Remember one sentence: dp[i][j] = dp[i-1][j] + dp[i][j-1], with edges all one, and the answer is the bottom-right cell.
---