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];}
};