64. Minimum Path Sum

！！！用dfs超时

class Solution {
public:
    int dir[2][2] = {{1,0},{0,1}};
    int minPathSum(vector<vector<int>>& grid) {
        int min = INT_MAX;
        int sum = grid[0][0];
        int m = grid.size();
        int n = grid[0].size();
        dfs(grid, 0,0, m, n, sum, min);
        return min;
    }
private:
    void dfs(vector<vector<int>>& grid, int x, int y, int m, int n, int sum, int& min){
        if(x == m - 1 && y == n - 1){
            int res = sum;
            if(min > res)
                min = res;
            return;
        }
        for(int i = 0; i < 2; i++){
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if(xx < 0 || xx >= m || yy < 0 || yy >= n)
                continue;
            dfs(grid, xx, yy, m, n, sum + grid[xx][yy], min);
        }
    }
};

用DP可以过，注意三目表达式的用法

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        vector<vector<int>> dp(grid);
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(i == 0 && j == 0)
                    continue;
                int left = (j - 1 >= 0) ? dp[i][j-1] : INT_MAX;
                int up = (i - 1 >= 0) ? dp[i - 1][j] : INT_MAX;
                dp[i][j] = min(left, up) + dp[i][j];
            }
        }
        return dp[grid.size() - 1][grid[0].size() - 1];
    }
};