Unique Paths

Problem

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Solution

2D Array DP

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) dp[i][j] = 1; //There is always only one way to reach border under the rules
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
            return dp[m - 1][n - 1];
        }
    }
}

Optimal 1D Array DP

public class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) return 0;
        if (m == 1 || n == 1) return 1;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[i - 1];
    }
}

Analysis

This is a very typical DP Problem
dp[i][j] represents how many unique paths to the grid [i][j]
For each grid, there are only paths from left or top, according to the rule
Except for the border, there is only one unique paths
At the end, we just need to return dp[m - 1][n - 1]

In the second solution, we optimize the 2D array to 1D
If you look at the updated statement in first solution, we update current dp with only its previous value
That is to say, we only need to record the previous value in dp rather than entire matrix
Hence we decreased the size from 2D to 1D