力扣：不同路径 (秒懂的动态规划)

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

输入1： m = 3 , n = 2
输出1：3
解释:从左上角开始，总共有 3 条路径可以到达右下角。
1: 向右 -> 向右 -> 向下
2: 向右 -> 向下 -> 向右
3: 向下 -> 向右 -> 向右
输入2：m = 7 , n = 2
输出2：28
来源：力扣 -- 不同路径

方案一 ：动态规划

1、 确定状态方程
我们使用一个二维数组 dp 来存储答案，dp[i][j]的值是从起始点（也就是(0,0)）走到(i, j)的路径数。
2、 确定状态转移方程
上面也说到，dp[i][j]的值就是从起始点（也就是(0,0)）走到(i, j)的路径数，那么如何求出这个值，我们就需要确定状态转移方程，我们思考一下，假设我们全都知道dp[i][j]的值，题目中说到，小机器人只能往右或者往下，那么dp[i][j]的值就是第 i 行第 j 列这个格子的上面那个格 子的值加上左边那个格子的值，也就是dp[i][j] = dp[i-1][j] + dp[i][j-1] ，因为这两个格子都可以走到dp[i][j]这个格子，那么他们的路径数之和就是dp[i][j]的值。
3、 确定边界条件
上面说到状态转移方程是dp[i][j] = dp[i-1][j] + dp[i][j-1]，那么当 i == 0 或者 j == 0 的时候会越界，而我们想一下，当 i == 0 或者 j == 0 的时候无外乎就是最上一行或者最左一列，我们在最上一行的路径数只能是一条（因为只能一直往左走），所以 dp[0][j]的值全为 1，同理最左一列的值也是1（因为只能一直往下走），其余的值按照状态转移方程就可以填满了，最后返回最右下角的值（dp[n-1][m-1]）就可以了。

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

方案二 ： 排列组合

我们要想到达终点，需要往下走n-1步，往右走m-1步，总共需要走n+m-2步。他无论往右走还是往下走他的总的步数是不会变的。
也就相当于总共要走n+m-2步，往右走m-1步总共有多少种走法，很明显这就是一个排列组合问题，公式如下

本题中需要求解的是

public int uniquePaths(int m, int n) {
    int N = n + m - 2;
    double res = 1;
    for (int i = 1; i < m; i++)
        res = res * (N - (m - 1) + i) / i;
    return (int) res;
}

相似题目
升级版：在路径中添加障碍物 -> 力扣：不同路径II
变形版：添加状态值(倒序dp) -> 力扣：地下城游戏