一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

62. 不同路径 - 中等 - 图1

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例 1:

输入: m = 3, n = 2

输出: 3

解释:

从左上角开始，总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下

  2. 向右 -> 向下 -> 向右

  3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3

输出: 28

提示：

1 <= m, n <= 100

题目数据保证答案小于等于 2 * 10 ^ 9

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/unique-paths

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

简单啊，做得太多了

回溯

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         int[][] memory = new int[m][n];
  4.         for(int i = 0; i < m; i++)
  5.             for(int j = 0; j < n; j++)
  6.                 memory[i][j] = -1;
  7.         return walk(0, 0, m, n, memory);
  8.     }
  10.     public int walk(int row, int column, int m, int n, int[][] memory){
  11.         if(row == m || column == n) return 0;
  12.         if(row == m-1 && column == n-1) return 1;
  13.         if(memory[row][column] != -1) return memory[row][column];
  14.         int sum = walk(row + 1, column, m, n, memory) + walk(row, column + 1, m, n, memory);
  15.         memory[row][column] = sum;
  16.         return sum;
  17.     }
  18. }

动态规划

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

        for(int j = 0; j < n; j++)
            dp[m-1][j] = 1;

        for(int k = n-2; k >= 0; k--)
            for(int z = m-2; z >= 0; z--)
                dp[z][k] = dp[z][k+1] + dp[z+1][k];

        return dp[0][0];

    }
}