Problem

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right or diagonally at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Examples

Example 1:

1
2
3
4

Input:
m = 3, n = 3
Output:
13

Solution

This problem is very similar to Unique Paths in Grid 1 - Count all paths moving right or down, just adding the diagonal bit.

Method 1 - Recursion

The recursive approach exhaustively tries all possible moves from each position until it either reaches the bottom-right corner (m-1, n-1) or goes out of bounds.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public class Solution {

	public int uniquePaths(int m, int n) {
		return dfs(0, 0, m, n);
	}

	private int dfs(int row, int col, int m, int n) {
		if (row == m - 1 && col == n - 1) return 1; // Reached destination
		if (row >= m || col >= n) return 0; // Out of bounds

		// Right + Down + Diagonal
		return dfs(row, col + 1, m, n) + dfs(row + 1, col, m, n) + dfs(row + 1, col + 1, m, n);
	}
}

Complexity

  • ⏰ Time complexity: O(3^(m+n)), because each call can lead to three other calls.
  • 🧺 Space complexity: O(n), assuming recursion stack

Method 2 - Top Down DP with Memoization

Top-down DP with memoization enhances the recursive approach by caching the results of subproblems. This prevents re-computation for the same cells multiple times.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {

	public int uniquePaths(int m, int n) {
		return findPaths(0, 0, m, n, new Integer[m][n]);
	}

	private int findPaths(int row, int col, int m, int n, Integer[][] memo) {
		if (row == m - 1 && col == n - 1) {
			return 1;
		}

		if (row >= m || col >= n) {
			return 0;
		}

		if (memo[row][col] != null) {
			return memo[row][col];
		}

		int right = findPaths(row, col + 1, m, n, memo);
		int down = findPaths(row + 1, col, m, n, memo);
		int diagonal = findPaths(row + 1, col + 1, m, n, memo);

		memo[row][col] = right + down + diagonal;
		return memo[row][col];
	}
}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(m*n)

Method 3 - Bottom up DP

Bottom-up DP constructs the solution iteratively using a table where dp[i][j] represents the number of ways to reach cell (i, j). Each cell in the dp table is filled based on the number of ways to reach the cell to its left, above it, and diagonally top-left.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {

	public int uniquePaths(int m, int n) {
		int[][] dp = new int[m][n];

		for (int i = 0; i < m; i++) {
			dp[i][0] = 1; // Only 1 way to go straight down
		}

		for (int j = 0; j < n; j++) {
			dp[0][j] = 1; // Only 1 way to go straight right
		}

		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] + dp[i - 1][j - 1]; // Down + Right + Diagonal
			}
		}

		return dp[m - 1][n - 1];
	}
}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(m*n)