动态规划基础：树型 DFS、回溯与记忆化搜索

1.2 70.爬楼梯 自底向上

当然也可以用自底向上：

• 每个节点不停向上返回，返回的是走到当前这一步的方案总数
• **归到根节点得出答案：**根节点是 n，叶子结点是 0
• 走到当前这一步的方案总数是前一个台阶和前两个台阶的方案总数之和
• 终止条件，也就是走到叶子节点，是到 0
• 注意：自底向上不是指根节点和叶子节点表示的含义与自顶向下相反，而是指递归中求出答案的过程是在递的过程还是归的过程
• 但是一般情况下，将目标作为根节点，0 作为叶子节点的写法确实都是自底向上
• 无论自顶向下还是自底向上，这个结果在大部分测试用例中超时。

class Solution { public: int climbStairs(int n) { auto dfs = [&](this auto&& dfs, int cur) -> int { if(cur == 0){ return 1; } if(cur < 0) return 0; int sum1 = dfs(cur-1); int sum2 = dfs(cur-2); return sum1 + sum2; }; return dfs(n); } };

1.3 70.爬楼梯 自底向上 + 记忆化

为什么没有自顶向下 + 记忆化？可以有，但是逻辑会很复杂，因为：

• 记忆化需要知道"从位置 cur 到终点 n 有多少种走法"
• 如果是 int 返回类型，函数可以直接返回这个值：return dfs(cur+1) + dfs(cur+2)
• 如果是 void 类型，函数无法告诉你这个值，只能通过副作用（修改 ans）间接计算

class Solution { public: int climbStairs(int n) { vector mem(n + 1, -1); auto dfs = [&](this auto&& dfs, int cur) -> int { if(cur == 0){ return 1; } if(cur < 0) return 0; if(mem[cur] != -1) return mem[cur]; int sum1 = dfs(cur-1); int sum2 = dfs(cur-2); mem[cur] = sum1 + sum2; return sum1 + sum2; }; return dfs(n); } };

2. 198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

2.1 自顶向下

对于当前的节点（房屋），有两个子节点：

• 选择当前房屋的钱，然后到下一个房屋，
• 放弃当前房屋的钱，然后到下下一个房屋。

总结：

• **根节点：**第一个房屋
• **叶子结点：**最后一个房屋或倒数第二个房屋
• **子节点：**下一个房屋或下下个房屋

class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); int ans = INT_MIN; int path = 0; auto dfs = [&](this auto&& dfs, int cur) -> void { if(cur >= n){ ans = max(ans, path); return; } path += nums[cur]; dfs(cur + 2); path -= nums[cur]; dfs(cur + 1); }; dfs(0); return ans; } };

2.2 自底向上

• **根节点：**最后一个房屋
• **子节点：**前一个房屋或前前个房屋
• **叶子结点：**第一个房屋或第二个房屋

class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); auto dfs = [&](this auto&& dfs, int cur) -> int { if(cur < 0) return 0; int sum1 = dfs(cur - 1); int sum2 = dfs(cur - 2) + nums[cur]; int sum = max(sum1, sum2); return sum; }; return dfs(n - 1); } };

2.3 记忆化

• **根节点：**最后一个房屋
• **子节点：**前一个房屋或前前个房屋
• **叶子结点：**第一个房屋或第二个房屋.
• **记忆：**从叶子节点到当前节点的最大和（多个叶子结点都表示第一个或第二个房屋，叶子节点不同，但是不同叶子节点代表的元素相同，可以理解为指针不同但值相同，每次从叶子节点返回时，已经有其他叶子节点返回过了，这时就可以复用值）

class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); vector<int> mem(n, -1); auto dfs = [&](this auto&& dfs, int cur) -> int { if(cur < 0) return 0; if(mem[cur] != -1) return mem[cur]; int sum1 = dfs(cur - 1); int sum2 = dfs(cur - 2) + nums[cur]; int sum = max(sum1, sum2); mem[cur] = sum; return sum; }; return dfs(n - 1); } };

3. 279.完全平方数

给你一个整数 n，返回 和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

3.1 自顶向下

• **根节点：**1
• **叶子结点：**路径和为 n 时的某个数
• **子节点：**从 1 开始到 sqrt(n - path) 内所有整数
• **终止条件：**当前路径总和 > 目标和
• 执行动作：计算当前路径 + 子节点值的路径和

class Solution { public: int numSquares(int n) { int curCount = 0; int path = 0; int ans = INT_MAX; auto dfs = [&](this auto&& dfs, int cur) -> void { if(path == n){ ans = min(curCount, ans); return; } if(path > n) return; for(int i = 1; i <= sqrt(n - path); i++){ curCount++; path += i*i; dfs(i); curCount--; path -= i*i; } }; dfs(1); return ans == INT_MAX ? 0 : ans; } };

3.2 自底向上

• **根节点：**表示和为 n
• **叶子结点：**0
• 子节点：从 1 开始到 sqrt(n - path) 内所有整数构建的和
• 终止条件：'递'到叶子节点，也就是和为 0

class Solution { public: int numSquares(int n) { auto dfs = [&](this auto&& dfs, int sum) -> int { if(sum == 0) return 0; if(sum < 0) return -1; int minCount = INT_MAX; for(int i = 1; i <= sqrt(sum); i++){ int count = dfs(sum - i * i); int curCount = count + 1; if(curCount > 0){ minCount = min(minCount, curCount); } } return minCount == INT_MAX ? -1 : minCount; }; return dfs(n); } };

3.3 记忆化

• **根节点：**n
• **叶子结点：**0
• 子节点：从 1 开始到 sqrt(n - path) 内所有整数构建的和
• 终止条件：'递'到叶子节点，也就是和为 0
• 记忆：从和为 0 的叶子结点到当前节点的所需完全平方数的最少数量（多个子节点值可能相同，如 3 下面有 1，4 下面有 1，2，从 0 到 1 这段路径就会被复用）

class Solution { public: int numSquares(int n) { vector<int> mem(n + 1, -1); auto dfs = [&](this auto&& dfs, int sum) -> int { if(sum == 0) return 0; if(sum < 0) return -1; if(mem[sum] != -1) return mem[sum]; int minCount = INT_MAX; for(int i = 1; i <= sqrt(sum); i++){ int count = dfs(sum - i * i); int curCount = count + 1; if(curCount > 0){ minCount = min(minCount, curCount); } } if(minCount == INT_MAX){ return -1; } mem[sum] = minCount; return minCount; }; return dfs(n); } };

4. 322.零钱兑换

给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

4.1 自顶向下

• **根节点：**第一个硬币
• **叶子节点：**不定，什么时候 和 > amount，谁就是叶子节点
• **子节点：**所有硬币

或者：

• **根节点：**和为 0
• **叶子节点：**和为 amount
• **子节点：**各个硬币构建的和

意思相同，可以当作一个结构体中多个不同字段

class Solution { public: int coinChange(vector<int>& coins, int amount) { int n = coins.size(); int ans = INT_MAX; long long path = 0; int curNum = 0; auto dfs = [&](this auto&& dfs, int cur) -> void { if(path == amount){ ans = min(ans, curNum); return; } if(path > amount) return; for(int i = 0; i < n; i++){ path += coins[i]; curNum++; dfs(i); path -= coins[i]; curNum--; } }; dfs(0); if(ans == INT_MAX) return -1; return ans; } };

4.2 自底向上

• 根节点：amount
• 叶子节点：0
• 子节点：所有硬币构建的和

class Solution { public: int coinChange(vector<int>& coins, int amount) { int n = coins.size(); auto dfs = [&](this auto&& dfs, int curSum, int cur) -> int { if(curSum == 0) return 0; if(curSum < 0) return -1; int minConis = INT_MAX; for(int i = 0; i < n; i++){ int res = dfs(curSum - coins[i], i); if(res != -1) minConis = min(minConis ,res + 1); } return minConis == INT_MAX ? -1 : minConis; }; return dfs(amount, 0); } };

4.3 记忆化搜索

• 根节点：amount
• 叶子节点：0
• 子节点：所有硬币构建的和
• 记忆：构建到当前节点代表的和时需要的最少硬币数量

class Solution { public: int coinChange(vector<int>& coins, int amount) { int n = coins.size(); vector<int> mem(amount + 1, -2); auto dfs = [&](this auto&& dfs, int curSum, int cur) -> int { if(curSum == 0) return 0; if(curSum < 0) return -1; if(mem[curSum] != -2) return mem[curSum]; int minConis = INT_MAX; for(int i = 0; i < n; i++){ int res = dfs(curSum - coins[i], i); if(res != -1) minConis = min(minConis ,res + 1); } mem[curSum] = minConis == INT_MAX ? -1 : minConis; return minConis == INT_MAX ? -1 : minConis; }; return dfs(amount, 0); } };