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


  • 0
    M

    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);

    code:

    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.