LeetCode64:Minimum Path Sum

LeetCode64:Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

這道題和前面很多題都好像。

解法一：

轉態A[i][j]可以表示左上點到grid[i][j]作為右下角的路徑的最小和，那麼它只依賴於A[i-1][j]和A[i][j-1]。狀態轉移方程是：
A[i][j]=min{A[i-1][j],A[i][j-1]}+grid[i][j]
需要注意的是邊界條件的處理，但是可以將A[i][j]的維數設置的比grid[i][j]的維數大1，這樣就可以將邊界統一起來了。
時間復雜度是O(M*N),M是矩陣的寬，N是矩陣的高。空間復雜度是O(M*N)。
runtime:28ms

class Solution {
public:
    int minPathSum(vector>& grid) {
        int height=grid.size();
        int width=grid[0].size();
        int current=0;
        vector > mask(height+1,vector(width+1,INT_MAX));
        for(int i=0;i

解法二：

解法一在空間上是可以做優化的，可以將空間復雜度降低為O(min(M,N))。
因為A[i][j]只依賴於A[i-1][j]和A[i][j-1]，所以可以只使用一個vector來存儲即可。
下面是按列進行掃描的算法，代碼來自：
https://leetcode.com/discuss/38360/easy-dp-solution-in-c-with-detailed-explanations-o-n-space

int minPathSum(vector>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector cur(m, grid[0][0]);
    for (int i = 1; i < m; i++)
        cur[i] = cur[i - 1] + grid[i][0];
    for (int j = 1; j < n; j++) {
        cur[0]  += grid[0][j];
        for (int i = 1; i < m; i++)
            cur[i] = min(cur[i - 1], cur[i]) + grid[i][j];
    }
    return cur[m - 1];
}