day159—动态规划—打家劫舍（LeetCode-198）

题目描述

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

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

示例 1：

输入：[1,2,3,1]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解决方案：

这段代码的核心功能是解决 “打家劫舍” 问题（即不能偷相邻房子的前提下，计算能偷到的最大金额），采用「类内辅助函数 + 记忆化递归」的思路实现，通过缓存子问题结果避免重复计算，大幅提升效率。

核心逻辑

1. 成员变量作用：

   • dx：记忆化数组（替代原代码的memo），缓存dfs(i)的计算结果，dx[i] = -1表示该位置未计算，避免重复递归；
   • nums_：类内备份的输入数组，供辅助函数dfs访问，无需递归传参。

2. 辅助递归函数dfs(i)逻辑：

   • 参数i：表示考虑 “从第 0 个到第i个房子” 的范围；
   • 递归边界：i < 0（没有房子可偷），返回 0；
   • 记忆化优化：若dx[i] != -1，说明该子问题已计算过，直接返回缓存值，避免重复递归；
   • 核心状态转移：dx[i] = max(dfs(i-1), dfs(i-2) + nums_[i])
     • 不偷第i个房子：最大金额 =dfs(i-1)（偷前i-1个房子的最大值）；
     • 偷第i个房子：最大金额 =dfs(i-2) + nums_[i]（偷前i-2个房子的最大值 + 第i个房子的金额）；
     • 取两者最大值存入dx[i]缓存，最终返回该值。

3. 主函数rob逻辑：

   • 边界处理：空数组直接返回 0，增强代码健壮性；
   • 初始化：将输入数组备份到nums_，初始化记忆化数组dx（长度为n，初始值 - 1）；
   • 启动递归：调用dfs(n-1)（从最后一个房子开始计算），返回最终结果。

关键特点

• 效率优化：记忆化数组dx将递归的时间复杂度从暴力枚举的O(2n)优化到O(n)；
• 封装性：辅助函数dfs设为类内函数，通过成员变量共享状态，无需传递大量参数；
• 逻辑清晰：核心是 “选 / 不选第i个房子” 的二选一决策，符合动态规划的状态转移思想。

总结

1. 核心思路：用记忆化递归缓存子问题结果，通过 “偷 / 不偷当前房子” 的状态转移计算最大金额；
2. 关键操作：dx数组的缓存是效率核心，避免重复计算相同子问题；
3. 功能效果：能高效求解打家劫舍问题，时间 / 空间复杂度均为O(n)，且代码结构符合 C++ 类编程风格。

函数源码：

#include<iostream> #include<string> #include<algorithm> using namespace std; int main() { int k; string s; char c1, c2; cin >> k; cin >> s >> c1 >> c2; int len = s.length(); int ans = 0; int ct = 0; int a = 0; int xfind = s.find_last_of(c1); int n = count(s.begin(), s.end(), c1); for (int i = a; i <= xfind; i++) { if (s[i] == c1) { ct++; if (ct > n) break; for (int j = i + k - 1; j < len; j++) { if (s[j] == c2) ans++; } } a = s.find(c1, a + 1); } cout << ans << endl; return 0; }