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

共以下 5 个回答

• JustRtn 普通 2023年9月18日 下午12:54

  class Solution {
  public:
      int minPathSum(vector>& grid) {
          int m = grid.size();
          int n = grid[0].size();
          vector> dp(m + 1, vector(n + 1, 201)); // 题目说明最大值不超过200
          dp[1][0] = dp[0][1] = 0;
          for (int i = 1; i <= m; i++) {
              for (int j = 1; j <= n; j++) {
                  dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
              }
          }
          return dp[m][n];
      }
  };
  

  class Solution {
  public:
      int minPathSum(vector<vector<int>>& grid) {
          int m = grid.size();
          int n = grid[0].size();
  
          vector<int> dp(n);
          dp[0] = grid[0][0];
          // 第一行可以直接赋值，只能向右走
          for (int i = 1; i < dp.size(); i++) {
              dp[i] = dp[i-1] + grid[0][i];
          }
          // 从第二行起，dp[0]值是上一轮dp[0]的值加上当前值（行首路径只能向下走）
          // 其他元素填充dp上一个值dp[j-1](向右路径)和dp上一轮的值dp[j](向下路径)的最小值加上当前值
          for (int i = 1; i < m; i++) {
              dp[0] += grid[i][0];
              for (int j = 1; j < n; j++) {
                  dp[j] = min(dp[j-1], dp[j]) + grid[i][j];
              }
          }
          return dp[n-1];
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 小肸 永久会员 2023年9月17日 下午2:38

  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];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 别扒拉我 普通 2023年9月12日 下午3:06

  1、动态规划（二维数组）
  一、状态定义：dp[i][j]为从左上角到grid[i][j]的最小路径和
  二、转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
  三、初始状态：dp[0][0]=grid[0][0]; for:dp[i][0] = dp[i-1][0] + grid[i][0]; for:dp[0][j] = dp[0][j-1] + grid[0][j]

  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];
      }
  }
  

  2、动态规划-空间优化（一维数组）

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

  “`java

  0 赞同 0 条回复

  登录以回复
• c 普通 2023年9月10日 下午11:49

  动态规划

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

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年9月10日 下午3:30

  dp[i][j]定义为从0，0到i，j的最短路径和

  class Solution {
      public int minPathSum(int[][] grid) {
          //处理特殊情况
          int m = grid.length;
          int n = grid[0].length;
          if (m <= 0 || n <= 0) {
              return 0;
          }
          int[] dp = new int[n];
          // 初始化
          dp[0] = grid[0][0];
          for (int j = 1; j < n; j++) {
              dp[j] = grid[0][j] + dp[j - 1];
          }
  
          // 递推式
          for (int i = 1; i < m; i++) {
              dp[0] = dp[0] + grid[i][0];
              for (int j = 1; j < n; j++) {
                  dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
              }
          }
          return dp[n-1];
      }
  }
  

  0 赞同 0 条回复

  登录以回复