p62

发表于 | 分类于 |

LeetCode p62 Unique Paths 题解

1.题目：

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?

题意：

从一个n*m棋盘的左上端点走到右下端点，有多少种走法。

2.解题思路:

见代码，数学问题，每次只能选择走右或者走下。
注意数据溢出。

3.代码

[title] [] [url] [link text]
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
 
public class Solution {
    public int uniquePaths(int m, int n) {
        m = m - 1;
		n = n - 1;
		if (m == 0 || n == 0) {
			return 1;
		}
		int a = m + n;
		int min = m < n ? m : n;
		long sum = 1;
		for (int i = 0; i < min; i++) {
			sum = sum * a;
			a--;
			// System.out.println(sum);
		}
		// System.out.println("=========");
		for (int i = 1; i <= min; i++) {
			sum = sum / i;
		}
		System.out.println(sum);
		return (int) sum;
    }
}

4.一些总结：