Leetcode 64. Minimum Path Sum

Minimum Path Sum : 要求在給定的一個二維數組中找到從左上角到右下角的一條最短路徑，並且該路徑上的每一步只能向右或向下移動。

Python (Minimum Path Sum)

方法:動態規劃

每個格子只能從它的上方或者左邊的格子走到，所以走到這個格子的最小值就是上方和左邊的兩個和取較小者，並加上當前的數值。

第一行的每個格子，只能從左邊走到，第一列的每個格子，只能從上方走到。

def minPathSum(self, grid):
        if not grid: return
        m, n = len(grid), len(grid[0])
        for i in range(1,m):
            grid[i][0] += grid[i-1][0]
        for j in range(1,n):
            grid[0][j] += grid[0][j-1]
        for i in range(1,m):
            for j in range(1,n):
                grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
        return grid[m-1][n-1]

C++

class Solution {
public:
	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 - 1][j], dp[i][j - 1]) + grid[i][j];
			}
	}
	return dp[m - 1][n - 1];
	}
};

時間複雜度：O(mn)，其中m和n分別為grid的行數和列數。
空間複雜度：O(mn)，使用了一個大小為mn的dp數組