leetcode动态规划系列(求路径篇）

目录

1、 不同路径

2、最小路径和

---

1、 不同路径

62.不同路径

题目描述：

 思路：看到路径直接就不多想就是动态规划，这道题是给定我们目标的坐标m和n，要我们求机器人能到达目标坐标的路径有多少条，机器人只能往下或者往右走一步，所以这个关系我们很容易找啊，dp[i][j] = dp[i-1][j] + dp[i][j-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 i = 0; i < n; i++) dp[0][i] = 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];
    }

此时时间复杂度O(m*n)，空间复杂度O(m*n) 

我们会发现，我们虽然用了一个二维数组来dp，但是只用了一次，我们为什么要浪费这么大的空间呢，完全可以转化为一个一维数组，dp[i] = dp[i] + dp[i-1]

 用一个一维数组代替原来的二维数组，极大程度的减少了我们耗费的空间！

我们进入代码：

public int uniquePaths(int m, int n) {
        //把pre[j]=cur[j]
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++)
                dp[j] += dp[j-1];
        }
        return dp[n-1];
    }

优化后的空间复杂度：O(m)

2、最小路径和

64.最小路径和

思路：老规矩，先确定解题方法，求路径用动态规划，这道题与咱们上一道讲解的不同路径和有点相似，大家可以先自己根据上一题的思路想想这道题；

咱们言归正传，先审题，这道题要我们求从左上角到右下角的最小路径和，关键点来了规定只能向下或者向右走一步，所以我们找最小路径和时，只需要比较上面位置的路径和左边位置的路径，即求dp[i][j] = grid[i][j] + Math.min(dp[i-1][j],dp[i][j-1])；

注：由于题目给定我们的是二维数组，我们可以不引入新的数组，可以直接在原来的数组grid上进行动态规划

我们直接进入代码：

public int minPathSum(int[][] grid) {
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (i == 0 && j == 0) continue;
            else if (j == 0) grid[i][j] += grid[i-1][j];
            else if (i == 0) grid[i][j] += grid[i][j-1];
            else grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
        }
    }
    return grid[grid.length-1][grid[0].length-1];
}

时间复杂度：O(m*n)

空间复杂度：O(1)

持续更新中~~