64. 最小路徑和：

給定一個包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說明：每次只能向下或者向右移動一步。

樣例 1：

輸入：
	
	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] <= 200

分析：

• 面對這道算法題目，二當(dāng)家的再次陷入了沉思。
• 這道題和62. 不同路徑和63. 不同路徑 II 有些類似，但是這次是尋找最優(yōu)解，由于每個位置的數(shù)值不一定是多少，所以同樣沒法使用數(shù)學(xué)公式直接計算。
• 那么動態(tài)規(guī)劃又成了此時的優(yōu)選。
• 從左上角出發(fā)，網(wǎng)格的第一行的每個元素只能從左上角元素開始向右移動到達(dá)，網(wǎng)格的第一列的每個元素只能從左上角元素開始向下移動到達(dá)，此時的路徑是唯一的，因此每個元素對應(yīng)的最小路徑和即為對應(yīng)的路徑上的數(shù)字總和。
• 其他的點只能從上或者從左到達(dá)，所以一個點的最優(yōu)路徑，一定經(jīng)過上面或者左面。從上到下，從左到右開始動態(tài)規(guī)劃，分解成了子問題。到達(dá)當(dāng)前點的最短路徑和，就是上面和左面點的最小路徑和中的較小值加上當(dāng)前點的值。
• 這里一樣可以使用滾動數(shù)組優(yōu)化空間。

題解：

rust：

impl Solution {
    pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
        let (rows, cols) = (grid.len(), grid[0].len());
        let mut dp = vec![0; cols];
        dp[0] = grid[0][0];
        (1..cols).for_each(|c| {
            dp[c] = dp[c - 1] + grid[0][c];
        });
        (1..rows).for_each(|r| {
            dp[0] += grid[r][0];
            (1..cols).for_each(|c| {
                dp[c] = dp[c].min(dp[c - 1]) + grid[r][c];
            });
        });
        return dp[cols - 1];
    }
}

go：

func minPathSum(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
	dp := make([]int, cols)
	dp[0] = grid[0][0]
	for c := 1; c < cols; c++ {
		dp[c] = dp[c-1] + grid[0][c]
	}
	for r := 1; r < rows; r++ {
		dp[0] += grid[r][0]
		for c := 1; c < cols; c++ {
			if dp[c-1] < dp[c] {
				dp[c] = dp[c-1] + grid[r][c]
			} else {
				dp[c] += grid[r][c]
			}

		}
	}
	return dp[cols-1]
}

c++：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        const int rows = grid.size(), cols = grid[0].size();
        int dp[cols];
        dp[0] = grid[0][0];
        for (int c = 1; c < cols; ++c) {
            dp[c] = dp[c - 1] + grid[0][c];
        }
        for (int r = 1; r < rows; ++r) {
            dp[0] += grid[r][0];
            for (int c = 1; c < cols; ++c) {
                dp[c] = min(dp[c], dp[c - 1]) + grid[r][c];
            }
        }
        return dp[cols - 1];
    }
};

python：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dp = [0] * cols
        for c in range(cols):
            dp[c] = dp[c - 1] + grid[0][c]
        for r in range(1, rows):
            dp[0] += grid[r][0]
            for c in range(1, cols):
                dp[c] = min(dp[c], dp[c - 1]) + grid[r][c]
        return dp[cols - 1]

java：

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

非常感謝你閱讀本文~
歡迎【點贊】【收藏】【評論】三連走一波~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進(jìn)步一點點~
本文由 二當(dāng)家的白帽子：https://le-yi.blog.csdn.net/ 博客原創(chuàng)~文章來源地址http://www.zghlxwxcb.cn/news/detail-612869.html

到了這里，關(guān)于算法leetcode｜64. 最小路徑和（rust重拳出擊）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！