第三週第四題 64. Minimum Path Sum，相較於前兩週 Easy 的題目可以很直覺的用一些邏輯方式解題，Medium 的題目就需要一點演算法基礎來對付，從這個過程也可以檢視不足的知識點來個別補強。今天這題是會給定一個陣列，需要算出從陣列最左上走到最右下的最短值是多少。
Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.
這題一開始思考如果只看左邊和上面誰比較大就直接選擇走的話會落入 local 最佳，但最不是 global 最佳的陷阱。Ex 1->1->4->2->1 反而是 9。
所以這題利用 DP 的概念，用一個陣列來記錄每個點的最小值，每個點參考的是上面和左邊的最小值，這樣一來就可以順利算出結果了。
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
vector<vector<int>> ans(grid.size(), vector<int>(grid[0].size()));
for(int i=0; i<grid.size(); i++) {
for(int j=0; j<grid[0].size(); j++) {
if(i == 0 && j == 0)
ans[i][j] = grid[i][j];
else if(i == 0)
ans[i][j] = grid[i][j] + ans[i][j-1];
else if(j == 0)
ans[i][j] = grid[i][j] + ans[i-1][j];
else
ans[i][j] = grid[i][j] + min(ans[i-1][j], ans[i][j-1]);
}
}
return ans[grid.size()-1][grid[0].size()-1];
}