LeetCode HOT100 - 最小路径和

DFS 如果不加记忆化会 T

所以用 dp

dp[i][j] 表示到 (i, j) 位置的最小花费

转移就是从 (i - 1, j) 或 (i, j - 1) 转移过来

时间复杂度 O(nm)

class Solution {
public:int minPathSum(vector<vector<int>>& a) {int n = a.size(), m = a[0].size();// auto dfs = [&](this auto&& self, int x, int y, int cur) -> void{//     if (x == n - 1 && y == m - 1) {//         ans = min(ans, cur);//         return;//     }//     if (x >= n || y >= m) {//         return;//     }//     if (x + 1 < n) self(x + 1, y, cur + a[x + 1][y]);//     if (y + 1 < m) self(x, y + 1, cur + a[x][y + 1]);// };// dfs(0, 0, a[0][0]);// return ans;vector<vector<int>> dp(n, vector<int>(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (i && j) {dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);} else if (i) {dp[i][j] = dp[i - 1][j];} else if (j) {dp[i][j] = dp[i][j - 1];}dp[i][j] += a[i][j];}} return dp[n - 1][m - 1];}
};