FilesExpand file tree

 master

/

UniquePaths62.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

77 lines (70 loc) · 2.1 KB

 master

/

UniquePaths62.java

Copy path

Top

File metadata and controls

• Code
• Blame

77 lines (70 loc) · 2.1 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

/**

* 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?

*

* https://leetcode.com/static/images/problemset/robot_maze.png

*

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

*

* Note: m and n will be at most 100.

*

*/

public class UniquePaths62 {

public int uniquePaths(int m, int n) {

if (m == 1 || n == 1) return 1;

int s = Math.min(m, n);

int l = Math.max(m, n);

int[][] dp = new int[s][l];

return uniquePaths(m, n, dp);

}

private int uniquePaths(int m, int n, int[][] dp) {

if (m == 1 || n == 1) return 1;

int s = Math.min(m, n);

int l = Math.max(m, n);

if (dp[s-1][l-1] != 0) return dp[s-1][l-1];

int a = uniquePaths(s-1, l, dp);

int b = uniquePaths(s, l-1, dp);

dp[s-1][l-1] = a + b;

return a + b;

}

public int uniquePaths2(int m, int n) {

int[] row = new int[n];

Arrays.fill(row,1);

for ( int i = 1; i < m; i++){

for ( int j = 1; j < n; j++){

row[j]+=row[j-1];

}

}

return row[n-1];

}

/**

* https://discuss.leetcode.com/topic/31724/java-solution-0ms-4lines

*/

public int uniquePaths3(int m, int n) {

long result = 1;

for(int i=0;i<Math.min(m-1,n-1);i++)

result = result*(m+n-2-i)/(i+1);

return (int)result;

}

/**

* https://discuss.leetcode.com/topic/23866/clean-and-simple-dp-java

*/

public int uniquePaths4(int m, int n) {

int[][] grid = new int[m][n];

for(int i = 0; i<m; i++){

for(int j = 0; j<n; j++){

if(i==0||j==0)

grid[i][j] = 1;

else

grid[i][j] = grid[i][j-1] + grid[i-1][j];

}

}

return grid[m-1][n-1];

}

}