Leetcode 62 不同路径

题意理解：

????????一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）

????????

? ? ? ? 要求：机器人只能向右走或向下走

? ? ? ? 目标：从起始位置走到终止位置有多少种路径

解题思路：

? ? ? ? 我们采用动态规划的思路来求解。

? ? ? ? 1.定义dp[i][j]表示从起始位置到(i,j)有多少种走法。

? ? ? ? 2.进入每个格子有两种方式，

????????????????第一种是从上面的格子走下来。

? ? ? ? ? ? ? ? 第二种是从左面的格子走到右边进入。

? ? ? ? ? ? ? ? 则可以得到递推公式：dp[i][j]=dp[i-1][j]+dp[i][j-1]

? ? ? ? 3.初始化：根据题意，有dp[i][0]=1,一直往下走；dp[j][0]一直往右走

? ? ? ? 4.遍历顺序，由于机器人只能往下|往右走，故遍历顺序：左->右，上->下

? ? ? ? 5.打印dp数组用于验证和debug

1.动态规划解题

  public int uniquePaths(int m, int n) {
        //定义存储
        int[][] dp=new int[m][n];
        //初始化
        for(int i=0;i<m;i++) dp[i][0]=1;
        for(int j=0;j<n;j++) dp[0][j]=1;
        //遍历顺序
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

2.分析

时间复杂度：O(m×n) 时间复杂度主要耗费在双for循环

空间复杂度：O(m×n) 主要空间耗费在动态数组dp上