# 【LeetCode】 64. Minimum Path Sum

## Description
> 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.

> 給一個`m` x `n`且用非負數填滿的網格，找到一條路徑從最左上到最右下且經過的數字總和最小。
> 提示：在任ㄏㄏㄏ你每次只能往下或往右移動

## 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.

## Solution

* 很簡單的數字迷宮，因為不能像四個方向移動，只需要簡單的DP即可解決。
* `dp[i][j]`紀錄到點`grid[i][j]`需要的最短步數。
* 遞迴式：
* 如果(`i`, `j`) = (0, 0)，`dp[i][j]` = `grid[i][j]`
* 如果`j = 0`，`dp[i][j]` = `dp[i - 1][j]`
* 如果`i = 0`，`dp[i][j]` = `dp[i][j - 1]`
* 其他，`dp[i][j]` = `min(dp[i - 1][j], dp[i][j - 1])`
* 不用DP應該也可以直接用BFS、DFS去走，不過不知道會不會超時。

### Code

class Solution {
public:
    int Step(int x, int y, vector<vector<int>>& grid, vector<vector<int>>& dp)
    {
        if(dp[y][x] == -1)
        {
            if(x == 0 && y == 0) dp[y][x] = grid[0][0];
            else if(x == 0) dp[y][x] = Step(x, y - 1, grid, dp) + grid[y][x];
            else if(y == 0) dp[y][x] = Step(x - 1, y, grid, dp) + grid[y][x];
            else dp[y][x] = min(Step(x, y - 1, grid, dp), Step(x - 1, y, grid, dp)) + grid[y][x];
        }
        return dp[y][x];
    }
    
    int minPathSum(vector<vector<int>>& grid) {
        int sx = grid[0].size();
        int sy = grid.size();
        vector<vector<int>> dp(sy, vector<int>(sx, -1));
        return Step(sx - 1, sy - 1, grid, dp);
    }
};

###### tags: `LeetCode` `C++`