【动态规划专题】LeetCode 64. 最小路径和

共以下 8 个回答

• 陆狗陆狗 普通 2024年12月25日 下午10:40

  解题思路
  – 定义dp[i][j] 在下标i和j的最小的路径上的数字总和
  – dp[i][j]=min(d[i-1][j]+grid[i][j],d[i][j-1]+grid[i][j])，但是上述的dp[i][j]必须左边和上边有元素，即不能是左边和上边的
  – 初始化[0][0]，还有左边和上边的
  【题解1】二维数组的dp

  class Solution {
      public int minPathSum(int[][] grid) {
          // 1、定义dp[i][j] 在下标i和j的最小的路径上的数字总和
          // 2、dp[i][j]=min(d[i-1][j]+grid[i][j],d[i][j-1]+grid[i][j])
          // 但是上述的dp[i][j]必须左边和上边有元素，即不能是左边和上边的
          // 3、初始化[0][0]，还有左边和上边的
          int[][] dp = new int[grid.length][grid[0].length];
          // 0列
          dp[0][0] = grid[0][0];
          for (int i = 1; i < grid.length; i++) {
              dp[i][0] = dp[i - 1][0] + grid[i][0];
          }
          // 0行
          for (int j = 1; j < grid[0].length; j++) {
              dp[0][j] = dp[0][j - 1] + grid[0][j];
          }
          // 剩余的部分
          for (int i = 1; i < grid.length; i++) {
              for (int j = 1; j < grid[0].length; j++) {
                  // 【错误点】写成了dp[i-1,j]
                  dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
              }
          }
          // 【错误点】对角点，需要-1
          return dp[grid.length - 1][grid[0].length - 1];
  
      }
  }
  

  • 错误点1：写成了dp[i-1,j]，应该是dp[i – 1][j]
  • 错误点2：【错误点】对角点，下标需要长度-1
  • 【题解2】一维数组的dp，关键是要先了解二维数组的dp，相当于第二行的dp用第一行的dp去存，就变成了一维

  class Solution {
      public int minPathSum(int[][] grid) {
          // 1、定义dp[i][j] 在下标i和j的最小的路径上的数字总和
          // 2、dp[i][j]=min(d[i-1][j]+grid[i][j],d[i][j-1]+grid[i][j])
          // 但是上述的dp[i][j]必须左边和上边有元素，即不能是左边和上边的
          // 3、初始化[0][0]，还有左边和上边的
          int[] dp = new int[grid[0].length];
          // 优化，下一行（除了最左边）=Min(上一行对应下标dp,相邻左边dp)+1
          dp[0] = grid[0][0];
          // 0行
          for (int j = 1; j < grid[0].length; j++) {
              dp[j] = dp[j - 1] + grid[0][j];
          }
          // 从第一行开始
          for (int i = 1; i < grid.length; i++) {
              for (int j = 0; j < grid[0].length; j++) {
                  // 每一行的第一列要单独处理一下
                  if (j == 0) {
                      dp[0] = dp[0] + grid[i][0];
                  } else {
                      dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
                  }
              }
  
          }
          return dp[grid[0].length - 1];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 晓宇 普通 2024年12月22日 下午9:03

  class Solution {
  public:
      // dp[i][j] 第（i，j）处最小路径和
      int minPathSum(vector<vector<int>>& grid) {
          int m = grid.size();
          int n = grid[0].size();
          vector<vector<int>> dp(m, vector<int>(n, 0));
          dp[0][0] = grid[0][0];
  
          for(int i = 1;i < m; i++)
              dp[i][0] = dp[i - 1][0] + grid[i][0];
  
          for(int j = 1;j < n; j++)
              dp[0][j] = dp[0][j - 1] + grid[0][j];    
  
  
          for(int i = 1; i < m; i++)
              for(int j = 1;j < n;j ++)
                  dp[i][j] = min(dp[i][j - 1],dp[i - 1][j]) + grid[i][j];
  
          return dp[m - 1][n - 1];
  
  
      }
      // o(n * m) o(n + m)
  };
  

  0 赞同 0 条回复

  登录以回复
• 秋山丽奈 普通 2024年12月22日 下午4:29

  思路 ：ans[i][j] = min(ans[i – 1][j], ans[i][j – 1]) + grid[i][j]

  class Solution {
  
      int row;
      int col;
      int min = Integer.MAX_VALUE;
      boolean[][] flag;
  
      public int minPathSum(int[][] grid) {
          // ans[i][j] = min(ans[i - 1][j], ans[i][j - 1]) + grid[i][j]
          this.row = grid.length;
          this.col = grid[0].length;
  
          for(int i = 1; i < this.col; i ++){
              grid[0][i] = grid[0][i-1] + grid[0][i];
          }
  
          for(int i = 1; i < this.row; i ++){
              grid[i][0] = grid[i-1][0] + grid[i][0];
          }
  
          for(int i = 1; i < this.row; i ++){
              for(int j = 1; j < this.col; j ++){
                  grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
              }
          }
          return grid[this.row-1][this.col-1];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 苯庸 普通 2024年12月21日 下午8:09

  class Solution {
  public int minPathSum(int[][] grid) {
  int m = grid.length, n = grid[0].length;
  int[][] dp = new int[m][n];
  dp[0][0] = grid[0][0];
  for(int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
  for(int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
  for(int i = 1; i < m; i++){
  for(int j = 1; j < n; j++){
  dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
  }
  }
  return dp[m-1][n-1];
  }
  }
  时间：O（mn）
  空间：O（mn）

  0 赞同 0 条回复

  登录以回复
• Kisara 普通 2024年12月20日 下午8:44

  优化前

  class Solution {
      public int minPathSum(int[][] grid) {
          int dp[][]=new int[grid.length][grid[0].length];
          dp[0][0]=grid[0][0];
          for(int i=1;i<grid.length;i++){
              dp[i][0]=dp[i-1][0]+grid[i][0];
          }
          for(int j=1;j<grid[0].length;j++){
              dp[0][j]=dp[0][j-1]+grid[0][j];
          }
  
          for(int i=1;i<grid.length;i++)
              for(int j=1;j<grid[0].length;j++){
                  dp[i][j]=Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
              }
  
          return dp[grid.length-1][grid[0].length-1];
      }
  }
  

  优化后

  class Solution {
      public int minPathSum(int[][] grid) {
          int[] dp=new int[grid[0].length];
          dp[0]=grid[0][0];
  
          for(int j=1;j<grid[0].length;j++){
              dp[j]=dp[j-1]+grid[0][j];
          }
  
          for(int i=1;i<grid.length;i++){
              dp[0]+=grid[i][0];
              for(int j=1;j<grid[0].length;j++){
                  dp[j]=Math.min(dp[j-1]+grid[i][j],dp[j]+grid[i][j]);
              }
          }
  
          return dp[grid[0].length-1];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Aatorx 永久会员 2024年12月20日 下午3:41

  class Solution {
  public:
      int minPathSum(vector<vector<int>>& grid) {
          int n = grid[0].size();
          vector<int> dp(n, 0);
          dp[0] = grid[0][0];
          for(int i = 1; i < n; i++) {
              dp[i] = dp[i - 1] + grid[0][i];
          }
          for(int i = 1; i < grid.size(); i++) {
              dp[0] = dp[0] + grid[i][0];
              for(int j = 1; j < n; j++) {
                  dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
              }
          }
          return dp[n - 1];
      }
  };
  

  时间复杂度O(N∗M)，空间复杂度O(N)。

  0 赞同 0 条回复

  登录以回复
• 月下足迹 普通 2024年12月20日 上午11:59

  class Solution {
  public int minPathSum(int[][] grid) {
  int m = grid.length;
  int n = grid[0].length;
  int [][] dp = new int [m][n];
  dp[0][0] = grid[0][0];
  //设定初始值
  for (int i = 1 ; i < m; i++) {
  dp[i][0] = dp[i -1][0] + grid[i][0];
  }
  for (int j = 1; j < n; j++) {
  dp[0][j] = dp[0][j – 1] + grid[0][j];
  }

      for (int i = 1; i < m; i++) {
          for (int j = 1; j < n ;j++) {
              dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
          }
      }
      return dp[m-1][n-1];
  }
  

  }

  0 赞同 0 条回复

  登录以回复
• Pendulumpal 普通 2024年12月19日 下午9:04

  基础O(n)

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

  0 赞同 0 条回复

  登录以回复