6 line Java DP solution 1ms

• ``````
public class Solution {

// https://leetcode.com/problems/unique-paths/

/*

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?

+---+---+---+---+---+---+---+---+
|ROB|   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |end|
+---+---+---+---+---+---+---+---+

*/

/*

// https://discuss.leetcode.com/topic/5623
// java-dp-solution-with-complexity-o-n-m

The assumptions are:

- When (n==0||m==0) the function always returns 1 since the robot
can't go left or up.

- For all other cells. The result = uniquePaths(m-1,n) + uniquePaths(m,n-1)

Therefore I populated the edges with 1 first and use DP to get the full 2-D array.

*/

/*

+----+----+----+----+----+----+----+----+
| 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  |
+----+----+----+----+----+----+----+----+
| 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  |
+----+----+----+----+----+----+----+----+
| 1  | 3  | 6  | 10 | 15 | 21 | 28 | 36 |
+----+----+----+----+----+----+----+----+
| 1  | 4  | 10 | 20 | 35 | 56 | 84 |120 |
+----+----+----+----+----+----+----+----+

*/

/*
public int uniquePaths(int m, int n) {
int[][] map = new int[m][n];

for(int i = 0; i < m; i++){
map[i][0] = 1;
}

for(int j = 0; j < n; j++){
map[0][j] = 1;
}

for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
map[i][j] = map[i-1][j] + map[i][j-1];
}
}

return map[m-1][n-1]; // the finish star.
}
*/

public int uniquePaths(int m, int n) {
int[]dp = new int[n];
dp[0] = 1;
for(int i = 0; i < m; i++)
for(int j = 1; j < n; j++)
dp[j] = dp[j] + dp[j-1];
return dp[n-1]; // the finish star.
}

}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.