Very Simple Way to Solve the Problem. It's a Combination Problem Actually. beats 80.93%

  • 0

    English Version

    First, let's review the problem again. The robot can only move either down or right. In another word, the total numbers of right and the total numbers of down are fixed.
    For example, Look at the picture, the robot must move down two times and move right six times. The problem is translated into How many different way that we insert two 'down' into six 'right'.
    alt text
    It's sounds like there are six red ball and two white ball. How many different way that we insert two white ball into six red ball?
    It's still very difficult.Let's change the problem again !
    There are eight ball, you need to choose two ball as white color or choose six ball as red ball !
    Here we are! the problem is toooooo easy. The result is C^2_8 .
    So the final result is C^(m-1)_(m+n-2);


    public class Solution {
        public int uniquePaths(int m, int n) {
    	m = m-1;n = n-1;
            double numerator = 1,denominator = 1;
    	int minNum = Math.min(m,n);
    	int maxNum = Math.max(m,n);
    	for(int i = (m + n); i > maxNum ; i --) numerator *= i;
    	for(int i = minNum; i > 0 ; i --) denominator *= i;
    	return (int)(numerator/denominator);


    alt text
    但是这个问题仍然不好解。那么我们再次转换问题,如果有8个球,我们有多少种方式选6个红球或者说选2个白球。这个问题太简单了,就是一个组合问题,结果就是C^6_8 或者C^2_8。
    那么延伸到m和n就是C^(m-1) _ (m+n-2) 或者 C^(n-1)_(m+n-2)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.