題目： LeetCode - 64. Minimum Path Sum

題目說明

給一個二維陣列，求從左上走到右下的最小數字和。

解題思路

因為只能往右邊走或往下面走，所以 走到每個點的最短距離 為 走到左邊的點的最短距離 和 走到上面的點的最短距離 取最小值，根據此想法做動態規劃即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int height = grid.size(), width = grid[0].size();
        vector<vector<int>> dp(height + 1, vector<int>(width + 1, INT_MAX));
        dp[0][1] = 0;
        for(int i = 1; i <= height; ++i)
            for(int j = 1; j <= width; ++j)
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];
        return dp[height][width];
    }
};