?
?
?
?
lc3665
class Solution {
public:
int uniquePaths(vector<vector<int>>& grid) {
const int MOD = 1'000'000'007;
int m = grid.size(), n = grid[0].size();
vector memo(m, vector(n, array<int, 2>{-1, -1})); // -1 表示沒有計算過
? ? ? ? auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
if (i < 0 || j < 0) { // 出界
return 0;
}
if (i == 0 && j == 0) { // 到達起點
return 1;
}
int& res = memo[i][j][k]; // 注意這里是引用
if (res != -1) { // 之前計算過
return res;
}
if (grid[i][j] == 0) { // 沒有鏡子，隨便走
res = (dfs(i, j - 1, 0) + dfs(i - 1, j, 1)) % MOD;
} else if (k == 0) { // 從下邊過來
res = dfs(i - 1, j, 1); // 反射到左邊
} else { // 從右邊過來
res = dfs(i, j - 1, 0); // 反射到上邊
}
return res;
};
? ? ? ? return dfs(m - 1, n - 1, 0); // 從終點出發
}
};
?
lc563
int dfs
ret += abs(leftSum - rightSum);?
?return node->val + leftSum + rightSum;?
class Solution {
? ? int ret = 0; // 存儲最終坡度總和
public:
? ? int findTilt(TreeNode* root) {
? ? ? ? dfs(root);
? ? ? ? return ret;
? ? }
? ??
? ? // 輔助函數：返回以 node 為根的子樹的總節點和，并計算當前節點的坡度
? ? int dfs(TreeNode* node) {
? ? ? ? if (node == nullptr) return 0; // 空節點，子樹和為 0
? ? ? ??
? ? ? ? int leftSum = dfs(node->left); // 左子樹和
? ? ? ? int rightSum = dfs(node->right); // 右子樹和
? ? ? ??
? ? ? ? ret += abs(leftSum - rightSum);?
? ? ? ? return node->val + leftSum + rightSum;?
? ? }
};
