62. Unique Paths

思路

不是用dfs或者bfs而是dp
grid[i][j]表示到达该位置的方法数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int uniquePaths(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-1][j] + grid[i][j-1];
			}
		}
	}
	return grid[m-1][n-1];
	
}