Description
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizesthe sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example: Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.
0
/ \
-3 9
/ /
-10 5
DP想法:
和62相似，這次每個路徑都會有weight，然後要找加總weight最小的
Algorithm:
1. Init: 將邊界值先加總
2. 令dp[i][j]為走到點i, j的最小權重總和 加上該點grid值
-> dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
1D DP想法：
用一條和cols數相同長度的array，先算好columns的邊界值 每次跑row時邊界值一樣先算好，接著再算出該相應col的dp