07/10 00:03

# 题目：62. 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?

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

Example 1:

```Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right```

Example 2:

```Input: m = 7, n = 3
Output: 28```

Constraints:

• `1 <= m, n <= 100`
• It's guaranteed that the answer will be less than or equal to `2 * 10 ^ 9`.

# 解题思路

```h(i,j) = h(i+1,j) + h(i,j+1) // 当i+1<=m-1，或j+1<=n-1时
h(i,j) = 0 // 当i+1>m-1（表示已经处于最右边的那一列格子），或j+1>n-1（表示已经处于最下面的那一行格子）时
h(m-1,n-1) = 1  // 表示右下角的格子```

# 最终实现

Java 实现

``````import java.util.Scanner;

public class Solution {

private int h[][];

public int uniquePaths(int m, int n) {
// initialize the two-dimension array h
h = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
h[i][j] = -1;
}
}
// set the right-bottom position to 1
h[m-1][n-1] = 1;
return calcH(0, 0);
}

private int calcH(int i, int j) {
int m = h.length;
int n = h[0].length;
if (i >= m || j >= n) {
return 0;
}
if (h[i][j] != -1) {
return h[i][j];
}
h[i][j] = calcH(i + 1, j) + calcH(i, j + 1);
return h[i][j];
}

public static void main(String[] args) {
Solution solution = new Solution();
Scanner scanner = new Scanner(System.in);
while(true) {
int m = scanner.nextInt();
int n = scanner.nextInt();
if (m == -1 || n == -1) {
break;
}
int res = solution.uniquePaths(m, n);
System.out.println(res);
}
scanner.close();
}

}``````

0
0 收藏

0 评论
0 收藏
0