题目描述

原题链接
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

示例 1：
image.png
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

    个人解法

Javascript

DP

经典DP问题

  1. /*
  2.  * @lc app=leetcode.cn id=64 lang=javascript
  3.  *
  4.  * [64] 最小路径和
  5.  */
  7. // @lc code=start
  8. /**
  9.  * @param {number[][]} grid
  10.  * @return {number}
  11.  */
  12.  var minPathSum = function (grid) {
  13.   const m = grid.length;
  14.   const n = grid[0].length;
  15.   for (let i = 0; i < m; i++) {
  16.     if (i === 0) {
  17.       for (let j = 1; j < n; j++) {
  18.         grid[i][j] = grid[i][j] + grid[i][j - 1];
  19.       }
  20.     } else {
  21.       grid[i][0] = grid[i][0] + grid[i - 1][0];
  22.     }
  23.   }
  24.   for (let i = 1; i < m; i++) {
  25.     for (let j = 1; j < n; j++) {
  26.       grid[i][j] = Math.min(grid[i][j - 1] + grid[i][j], grid[i - 1][j] + grid[i][j]);
  27.     }
  28.   }
  29.   return grid[m - 1][n - 1];
  30. };
  31. // @lc code=end

Java

动态规划

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         int m= grid.length,n=grid[0].length;
  4.         int[][] dp=new int[m][n];
  5.         dp[0][0]=grid[0][0];
  6.         for (int i=1;i<m;i++){
  7.             dp[i][0]=dp[i-1][0]+grid[i][0];
  8.         }
  9.         for (int j=1;j<n;j++){
  10.             dp[0][j]=dp[0][j-1]+grid[0][j];
  11.         }
  12.         for (int i=1;i<m;i++){
  13.             for (int j=1;j<n;j++){
  14.                 dp[i][j]=grid[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);
  15.             }
  16.         }
  17.         return dp[m-1][n-1];
  18.     }
  19. }

其他解法

Java

Javascript