动态规划--不同的路径

114. 不同的路径

有一个机器人的位于一个 m × n 个网格左上角。

机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。

问有多少条不同的路径？

样例

给出 m = 3 和 n = 3, 返回 6.
给出 m = 4 和 n = 5, 返回 35.

注意事项

n和m均不超过100

解题思路：终于自己做出了一道这样的题目（这次没有参考），是真的开心。

刚做这个题目的时候，自己先在本子上画了画路径，并举了几个例子，发现没有什么联系。想想前面的几道题目，都会对第一行和第一列进行处理。在这个题目中，到达第一行或者第一列都会只有一种路径，而到达（i,j）位置的路径数，就是（i-1，j）位置和（i,j-1）位置的相加的和（这个自己举个例子就可以理解了）。

代码：

public class Solution {
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int uniquePaths(int m, int n) {
        // write your code here
        if(m==0||n==0)
            return 0;
        int[][] res= new int[m][n];
        for(int i=0;i<m;i++)
            res[i][0] = 1;
        for(int j=0;j<n;j++)
            res[0][j] = 1;
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
                res[i][j] = res[i-1][j]+res[i][j-1];
        return res[m-1][n-1];
        
    }
}

代码交上去对了，确实有点开心，但是自己设计的太耗时。。。

对自己的代码做出如下优化：

public class Solution {
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int uniquePaths(int m, int n) {
        // write your code here
        if(m==0||n==0)
            return 0;
        /*
        int[][] res= new int[m][n];
        for(int i=0;i<m;i++)
            res[i][0] = 1;
        for(int j=0;j<n;j++)
            res[0][j] = 1;
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
                res[i][j] = res[i-1][j]+res[i][j-1];
        return res[m-1][n-1];*/
        int dp[] = new int[n];
        for(int i=0;i<n;i++)
            dp[i] = 1;
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
                dp[j]+=dp[j-1];
        return dp[n-1];
        
    }
}

改完之后，在提交：

在网上百度了一波，原来是一道排列组合问题。

解释如下：

机器人总共走m+n-2步，其中m-1步往下走，n-1步往右走，本质上就是一个组合问题，也就是从m+n-2个不同元素中每次取出m-1个元素的组合数。根据组合的计算公式，我们可以写代码来求解即可。代码如下：

public int uniquePaths(int m, int n) {
    double dom = 1;
    double dedom = 1;
    int small = m<n? m-1:n-1;
    int big = m<n? n-1:m-1;
    for(int i=1;i<=small;i++)
    {
        dedom *= i;
        dom *= small+big+1-i;
    }
    return (int)(dom/dedom);
}

上面的代码求解了组合的结果，只需要做一次行或者列的扫描，所以时间复杂度是O(min(m,n))，而空间复杂度是O(1)。比起上面的两种解法更优。不过这里有个弊端，就是如果代码中的dom和dedom如果不是double，而是用int，那么会很容易越界，因为这是一个阶乘，所以大家在面试中讨论这种方法要注意和提及越界的问题。

来源：https://blog.csdn.net/linhuanmars/article/details/22126357