62. 不同路径 java解决

题目描述：

难度：中等
相关标签：数学、动态规划、组合数学

一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
    输入：m = 3, n = 7
    输出：28
示例 2：
    输入：m = 3, n = 2
    输出：3
    解释：
        从左上角开始，总共有 3 条路径可以到达右下角。
        1. 向右 -> 向下 -> 向下
        2. 向下 -> 向下 -> 向右
        3. 向下 -> 向右 -> 向下
示例 3：
    输入：m = 7, n = 3
    输出：28
示例 4：
    输入：m = 3, n = 3
    输出：6
提示：
    1 <= m, n <= 100
    题目数据保证答案小于等于 2 * 109

最开始，我以为用递归不会超时，没想到还是超时了，果然没那么简单呐，呜呜呜~

class Solution {
    public int uniquePaths(int m, int n) {
        if ( m == 1 || n == 1 )
            return 1;
 
        return uniquePaths( m - 1, n ) + uniquePaths( m, n - 1 );
    }
}

正确方法：

一样的核心算法:

        走到的该位置的路径数 = 走到左一格的位置的路径数 + 走到上一格的路径数

        即：dp[ i ][ j ] = dp[ i -1 ][ j ] + dp[ i ][ j - 1 ]

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[ 0 ][ 0 ] = 1;
        for ( int i = 0; i < m; i ++ ) {
            for ( int j = 0; j < n; j ++ ) {
                if ( i == 0 || j == 0 )
                    dp[ i ][ j ] = 1;
                else
                    dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1 ];
            }
        }
        return dp[ m - 1 ][ n - 1];
    }
}

力扣上的另一道在此题基础上加上了 障碍 的题

(75条消息) 63. 不同路径 II java解决_其然乐衣的博客-CSDN博客