【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++