LeetCode Unique Paths

LeetCode 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 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.


问从左上角走到右下角一共有多少种方案,每次只能往右或者下走。很简单的题,高中学过排列组合的都知道。

假设右下和左上的坐标之差为(x,y),则从左上走到右下一共需要走x+y步,可以分为x步往右走,y步往下走。每一步都可以选择往右或者往下走,所以总的方案数为C_{x+y}^x==C_{x+y}^y,用x,y中的较小者来算就可以了,计算方法就是高中数学老师教的啦:-)

完整代码如下

class Solution {
public:
	int uniquePaths(int m, int n) {
		int x = m - 1, y = n - 1;
		int z = x + y, u = x < y ? x : y;
		double ans = 1.0;
		for (int i = 1; i <= u; i++) {
			ans *= z;
			ans /= i;
			z--;
		}
		return ans;
	}
};

本代码提交AC,用时0MS。

One thought on “LeetCode Unique Paths

  1. Pingback: LeetCode Unique Paths II | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *