forked from algorithm009-class01/algorithm009-class01
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathUniquePaths.java
More file actions
31 lines (27 loc) · 898 Bytes
/
UniquePaths.java
File metadata and controls
31 lines (27 loc) · 898 Bytes
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
package dynamic;
import java.util.Arrays;
public class UniquePaths {
public int uniquePaths(int m,int n){
/**
* 令dp[i][j]是到达i,j最多路径
* 动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
* 对于第一行dp[0][j],或者第一列dp[i][0],由于都是在边界，所以只能为1
* 因为我们每次只需要dp[i-1][j],dp[i][j-1]，所以每次只要记录这两个数;
*/
int[] cur = new int[n];
Arrays.fill(cur,1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
cur[j] += cur[j-1];
}
}
return cur[n-1];
}
public static void main(String[] args) {
int m = 3;
int n = 2;
UniquePaths uniquePaths = new UniquePaths();
int r = uniquePaths.uniquePaths(m,n);
System.out.println(r);
}
}