LeetCode — 最小路径和

问题陈述

给定一个 mxn网格 用非负数填充，找到一条从左上角到右下角的路径，该路径最小化沿其路径的所有数字的总和。

笔记： 您只能在任何时间点向下或向右移动。

问题陈述取自： https://leetcode.com/problems/minimum-path-sum

示例 1：

Source: LeetCode

 输入：网格 = [[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 == 网格[i].length  
 - 1 <= 米，n <= 200  
 - 0 <= 网格[i][j] <= 100

解释

蛮力方法

蛮力方法是生成从左上角到右下角的所有可能路径。我们计算所有这些路径的总和并找到最小值。该解决方案适用于小型阵列，但对于大型阵列会超时。

最优子结构

到达 (m, n) 的路径必须通过以下两个单元之一：(m – 1, n) 或 (m, n – 1)。到达（m，n）的最小成本可以计算为“两个单元格的最小值加上网格（m，n）”。

 minimumCost(m, n) = min(minimumCost(m - 1, n), minimumCost(m, n - 1)) + grid(m, n) int minCost(int grid[R][C], int m, int n)  
 {  
 如果 (n < 0 || m < 0)  
 返回 INT_MAX；  
 否则如果 (m == 0 && n == 0)  
 返回网格[m][n]；  
 别的  
 返回网格[m][n] +  
 分钟（  
 minCost（网格，m - 1，n），  
 minCost（网格，m，n - 1）  
 );  
 }

动态规划

使用递归方法求解上述最优子结构。但是，如果我们仔细观察，上述方法会一次又一次地计算相同的子问题。

我们可以避免使用动态规划方法重新计算相同的子问题。我们创建一个二维数组并以自下而上的方式解决问题。

让我们跳到算法以更好地理解它。

 - 设置 m = grid.size()  
 n = 网格[0].size()  
 dp(m, 向量<int>(n))  
  
 - 循环 i = 0;我 < 米;我++  
 j = 0 的循环； j  
  
 如果我 == 0 && j == 0  
 - 设置 dp[i][j] = 网格[i][j]  
 否则如果我 == 0  
 - 设置 dp[i][j] = dp[i][j - 1] + grid[i][j]  
 否则如果 j == 0  
 - 设置 dp[i][j] = dp[i - 1][j] + grid[i][j]  
 别的  
 - 设置 dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]  
 - 结束  
  
 - 返回 dp[m - 1][n - 1]

这种方法的时间复杂度是 O(N^2) ，空间复杂度为 O(M*N) .

让我们检查一下我们的算法 C++ , 戈朗 ， 和 Javascript .

C++ 解决方案

 类解决方案{  
 上市：  
 int minPathSum(向量<vector<int> >＆网格）{  
 int m = grid.size();  
 int n = grid[0].size();  
 向量<vector<int> > dp(m, 向量<int>(n))；  
  
 for(int i = 0; i < m; i++) {  
 for(int j = 0; j < n; j++) {  
 如果（我 == 0 && j == 0）{  
 dp[i][j] = 网格[i][j];  
 } 否则如果（我 == 0）{  
 dp[i][j] = dp[i][j - 1] + 网格[i][j];  
 }否则如果（j == 0）{  
 dp[i][j] = dp[i - 1][j] + 网格[i][j];  
 } 别的 {  
 dp[i][j] = min(dp[i- 1][j], dp[i][j - 1]) + 网格[i][j];  
 }  
 }  
 }  
  
 返回 dp[m - 1][n - 1]；  
 }  
 };

Golang 解决方案

 func minPathSum(grid [][]int) int {  
 m := 长度（网格）  
 n := len(grid[0])  
 dp := make([][]int, m)  
  
 对于 k := 范围 dp {  
 dp[k] = make([]int, n)  
 }  
  
 对于我：= 0；我 < 米;我++ {  
 对于 j := 0; j < n; j++ {  
 如果我 == 0 && j == 0 {  
 dp[i][j] = 网格[i][j]  
 } 否则如果我 == 0 {  
 dp[i][j] = dp[i][j - 1] + 网格[i][j]  
 } 否则如果 j == 0 {  
 dp[i][j] = dp[i - 1][j] + 网格[i][j]  
 } 别的 {  
 dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 网格[i][j]  
 }  
 }  
 }  
  
 返回 dp[m - 1][n - 1]  
 }  
  
 func min(a, b int) int {  
 如果 a < b {  
 返回一个  
 }  
 返回 b  
 }

Javascript 解决方案

 var minPathSum = 函数（网格）{  
 让 m = grid.length;  
 让 n = grid[0].length;  
 让 dp = 新数组（m）；  
  
 for(让 k = 0; k < dp.length; k++) {  
 dp[k] = 新数组（n）；  
 }  
  
 for(让 i = 0; i < m; i++) {  
 for(让 j = 0; j < n; j++) {  
 如果（我 == 0 && j == 0）{  
 dp[i][j] = 网格[i][j];  
 } 否则如果（我 == 0）{  
 dp[i][j] = dp[i][j - 1] + 网格[i][j];  
 }否则如果（j == 0）{  
 dp[i][j] = dp[i - 1][j] + 网格[i][j];  
 } 别的 {  
 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];  
 }  
 }  
 }  
  
 返回 dp[m - 1][n - 1]；  
 };

让我们空运行我们的算法 示例 2 .

 输入：grid = [[1, 2, 3], [4, 5, 6]]  
  
 第 1 步：m = grid.size()  
 = 2  
 n = 网格[0].size()  
 = 3  
  
 dp(2, 3)  
  
 第 2 步：循环 i = 0；我 < 米  
 0 < 2  
 真的  
  
 j = 0 的循环； j < n  
 0 < 3  
 真的  
  
 如果我 == 0 && j == 0  
 真的  
  
 dp[i][j] = 网格[i][j]  
 = 网格[0][0]  
 = 1  
  
 dp = [[1, 0, 0], [0, 0, 0]]  
  
 j++  
  
 j = 1  
 j < n  
 1 < 3  
 真的  
  
 如果我 == 0 && j == 0  
 真的  
 否则如果我 == 0  
 真的  
  
 dp[i][j] = dp[i][j - 1] + 网格[i][j]  
 = dp[0][1 - 1] + 网格[0][1]  
 = dp[0][0] + 网格[0][1]  
 = 1 + 2  
 = 3  
  
 dp = [[1, 3, 0], [0, 0, 0]]  
  
 j++  
 j < n  
 2 < 3  
 真的  
  
 如果我 == 0 && j == 0  
 真的  
 否则如果我 == 0  
 真的  
  
 dp[i][j] = dp[i][j - 1] + 网格[i][j]  
 = dp[0][2 - 1] + 网格[0][1]  
 = dp[0][1] + 网格[0][2]  
 = 3 + 3  
 = 6  
  
 dp = [[1, 3, 6], [0, 0, 0]]  
  
 j++  
 j < n  
 3 < 3  
 错误的  
  
 我++  
 我 = 1  
  
 第 3 步：循环 i < m  
 1 < 2  
 真的  
  
 j = 0 的循环； j < n  
 0 < 3  
 真的  
  
 如果我 == 0 && j == 0  
 错误的  
 否则如果我 == 0  
 错误的  
 否则如果 j == 0  
 真的  
  
 dp[i][j] = dp[i - 1][j] + 网格[i][j]  
 = dp[1 - 1][0] + 网格[1][0]  
 = dp[0][0] + 网格[1][0]  
 = 1 + 4  
 = 5  
  
 dp = [[1, 3, 6], [5, 0, 0]]  
  
 j++  
 j < n  
 1 < 3  
 真的  
  
 如果我 == 0 && j == 0  
 错误的  
 否则如果我 == 0  
 错误的  
 否则如果 j == 0  
 错误的  
 别的  
  
 dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 网格[i][j]  
 = min(dp[1][1 - 1], dp[1 - 1][1]) + 网格[1][1]  
 = min(dp[1][0], dp[0][1]) + 5  
 = min(5, 3) + 5  
 = 3 + 5  
 = 8  
  
 dp = [[1, 3, 6], [5, 8, 0]]  
  
 j++  
 j < n  
 2 < 3  
 真的  
  
 如果我 == 0 && j == 0  
 错误的  
 否则如果我 == 0  
 错误的  
 否则如果 j == 0  
 错误的  
 别的  
  
 dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + 网格[i][j]  
 = min(dp[1][2 - 1], dp[1 - 1][2]) + 网格[1][2]  
 = min(dp[1][1], dp[0][2]) + 6  
 = min(8, 6) + 6  
 = 6 + 6  
 = 12  
  
 dp = [[1, 3, 6], [5, 8, 12]]  
  
  
 j++  
 j < n  
 3 < 3  
 错误的  
  
 我++  
 我 = 2  
  
 第 4 步：循环 i < m  
 2 < 2  
 错误的  
  
 第 5 步：返回 dp[m - 1][n - 1]  
 dp[2 - 1][3 - 1]  
 dp[1][2]  
 12  
  
 我们将答案返回为 12。

最初发表于 https://alkeshghorpade.me .

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明

本文链接：https://www.qanswer.top/1356/49232905