打家劫舍与最长有效括号：动态规划与字符串处理的双重魅力

博客引言：

在我们的生活中，算法无处不在，它不仅帮助我们解决复杂的问题，还能揭示隐藏在数据背后的规律。今天，我们将通过两个有趣的问题，探索算法在动态规划与字符串处理中的智慧。

首先，我们将探讨打家劫舍问题，看看如何通过动态规划找到偷窃的最大金额。接着，我们将分析最长有效括号问题，探讨如何通过栈结构高效找到最长的有效括号子串。通过这两个案例，你将看到算法如何在实际问题中发挥作用，帮助我们找到最优解。

让我们一起进入算法的世界，探索这些隐藏在动态规划与字符串处理背后的智慧！

博客正文：

第一章：神偷的夜行秘籍——《打家劫舍》

🎭 剧情设定：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，但相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算在不触动警报的情况下，一夜之内能够偷窃到的最高金额。

算法核心：动态规划
这个问题可以通过动态规划来解决。动态规划是一种通过将问题分解为更小的子问题来解决复杂问题的方法。具体来说，我们可以定义一个状态数组，记录到第i个房屋时的最大偷窃金额。

🔍 核心矛盾

• 贪婪陷阱：若只选金额最大的房屋，可能因相邻限制错失全局最优。

• 连锁反应：每个选择影响后续所有可能性（动态规划的典型特征）。

⚙️ 动态规划的精髓解析

1. 状态定义：定义一个数组 dp，其中 dp[i] 表示到第i个房屋时的最大偷窃金额。
2. 状态转移：对于每个房屋i，有两种选择：
   • 偷窃第i个房屋：那么不能偷窃第i-1个房屋，最大金额为 dp[i-2] + nums[i]。
   • 不偷窃第i个房屋：那么最大金额为 dp[i-1]。 因此，状态转移方程为：

dp[i] = max( dp[i-1], dp[i-2] + nums[i] )

1. 初始化：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。

• dp[i-1]：不偷第 i 间，继承前 i-1 间的最优解。

• dp[i-2] + nums[i]：偷第 i 间，跳过 i-1 间，取前 i-2 间的最优解加当前收益。

🌰 实例推演（输入 [2,7,9,3,1]）

1. 初始化：dp[0]=2（偷第1间），dp[1]=max(2,7)=7（第1、2间选更大者）。

2. 状态转移：

   • dp[2] = max(dp[1], dp[0]+9) = max(7, 2+9)=11

   • dp[3] = max(dp[2], dp[1]+3) = max(11, 7+3)=11

   • dp[4] = max(dp[3], dp[2]+1) = max(11, 11+1)=12

3. 终局：输出 12，对应偷第1、3、5间。

💡 算法哲学：每个局部最优解都是全局最优解的基石，拒绝短视贪婪，方成“盗亦有道”。

#include <stdio.h>   // 引入标准输入输出库，用于printf和scanf等函数
#include <stdlib.h>  // 引入标准库，用于内存分配malloc和free等函数// 函数：计算可偷窃的最大金额
// 参数：nums - 整型数组指针，表示每个房屋的金额
//       numsSize - 数组长度
// 返回值：可偷窃的最大金额
int rob(int* nums, int numsSize) {// 处理特殊情况：空数组if (numsSize == 0) return 0;  // 如果没有房屋，返回0// 处理特殊情况：只有一个房屋if (numsSize == 1) return nums[0];  // 如果只有一个房屋，直接返回其金额int prevMax = nums[0];  // 初始化前前个房屋的最大收益（即第0个房屋的收益）// 初始化前个房屋的最大收益（比较第0个和第1个房屋的收益）int currentMax = (nums[0] > nums[1]) ? nums[0] : nums[1];// 从第三个房屋开始动态规划（索引2开始）for (int i = 2; i < numsSize; i++) {int temp = currentMax;  // 临时保存当前最大值（用于后续更新prevMax）// 状态转移方程：// 比较两种选择：偷当前房屋（prevMax + nums[i]）或不偷（currentMax）currentMax = (currentMax > prevMax + nums[i]) ? currentMax : prevMax + nums[i];prevMax = temp;  // 更新前前个房屋的最大收益为前次计算的currentMax}return currentMax;  // 返回最终计算的最大金额
}int main() {int n;  // 定义变量：房屋数量printf("请输入房屋数量：");  // 提示用户输入scanf("%d", &n);  // 读取用户输入的房屋数量// 输入验证：确保房屋数量是正整数if (n <= 0) {printf("错误：房屋数量必须为正整数！\n");  // 错误提示return 1;  // 非正常退出}// 动态分配内存：创建存储房屋金额的数组// 分配 n 个整型大小的内存空间int* nums = (int*)malloc(n * sizeof(int));// 检查内存分配是否成功if (nums == NULL) {printf("内存分配失败！\n");  // 内存分配失败提示return 1;  // 非正常退出}// 提示用户输入房屋金额printf("请输入%d个房屋的金额（用空格分隔）：", n);// 循环读取用户输入的每个房屋金额for (int i = 0; i < n; i++) {scanf("%d", &nums[i]);  // 将输入值存储到数组相应位置}// 调用rob函数计算最大可偷窃金额int result = rob(nums, n);// 输出计算结果printf("最大可偷窃金额为：%d\n", result);free(nums);  // 释放动态分配的内存，防止内存泄漏return 0;  // 正常退出程序
}

输出结果：

---

第二章：括号猎人的密码战——《最长有效括号》

🎭 剧情设定
你面对一串混乱的括号序列 (()))())，需找出最长连续有效子串（如 ()() 有效， ()) 无效）。

算法核心：栈结构与括号匹配
这个问题可以通过栈结构来解决。栈结构可以帮助我们记录有效括号的位置，从而计算最长的有效长度。

详细分析：

1. 初始化栈：栈用于记录括号的位置，初始时栈中放入一个-1作为基准。
2. 遍历字符串：对于每个字符，如果是 '('，则将其索引压入栈中；如果是 ')'，则弹出栈顶元素。如果栈为空，将当前索引压入栈中作为新的基准；否则，计算当前索引与栈顶元素的差值，更新最长有效长度。
3. 返回结果：遍历完成后，最长有效长度即为所求。

🔍 核心矛盾

• 连续性要求：有效括号必须连续（如 ()(()) 的最长有效子串是后4位 (())）。

• 嵌套干扰：左括号 ( 可能被后续 ) 匹配，也可能因位置错误失效。

⚙️ 动态规划的进阶技巧
定义 dp[i] 为以第 i 个字符结尾的最长有效括号长度：

• Case 1：s[i] = '('
  直接置 dp[i]=0（有效括号必以 ) 结尾）。

• Case 2：s[i] = ')'`

  1. 前一位是 '('：形如 ...() ，则 dp[i] = dp[i-2] + 2。

  2. 前一位是 ')'：形如 ...)) ，则需检查 s[i - dp[i-1] - 1] 是否为 (：

     • 若是，则 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]（跨过已匹配的子串）。

🌰 实例推演（输入 ")()())"）

1. 初始化：dp = [0,0,0,0,0,0]

2. 逐步计算：

   • i=1: s[1]='(' → dp[1]=0

   • i=2: s[2]=')' 且 s[1]='(' → dp[2]=dp[0]+2=2

   • i=3: s[3]='(' → dp[3]=0

   • i=4: s[4]=')' 且 s[3]='(' → dp[4]=dp[2]+2=4

   • i=5: s[5]=')'，前一位 s[4]=')'，检查 s[5 - dp[4] - 1] = s[0]=')' → 无效，dp[5]=0

3. 终局：最大值为 4（子串 ()()）。

💡 算法哲学：括号匹配是“时空对称”的艺术，动态规划通过保存历史状态，破解嵌套中的时空连续性。

#include <stdio.h>   // 引入标准输入输出库，用于printf和fgets等函数
#include <stdlib.h>  // 引入标准库，用于内存分配malloc和free等函数
#include <string.h>  // 引入字符串处理库，用于strlen和strcspn等函数// 函数：计算最长有效括号子串长度
// 参数：s - 字符指针，指向包含括号的字符串
// 返回值：最长有效括号子串的长度
int longestValidParentheses(char* s) {int n = strlen(s);  // 计算输入字符串的长度if (n <= 1) return 0; // 长度小于2不可能有有效括号，直接返回0// 创建动态规划数组 dp[i]表示以s[i]结尾的最长有效括号长度int* dp = (int*)malloc(n * sizeof(int));  // 动态分配n个整数大小的内存空间if (!dp) {  // 检查内存分配是否成功printf("内存分配失败！\n");  // 内存分配失败提示exit(1);  // 退出程序}// 初始化dp数组所有元素为0memset(dp, 0, n * sizeof(int));  // 使用memset将整个数组初始化为0int maxLen = 0; // 记录最大长度的变量，初始化为0// 动态规划计算：从索引1开始遍历字符串for (int i = 1; i < n; i++) {if (s[i] == ')') {  // 当前字符是右括号时才可能形成有效括号对// 情况1: 前一个字符是 '('，形如 "...()"if (s[i - 1] == '(') {  // 检查前一个字符是否是左括号dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;  // 如果i>=2，加上前前位置的dp值再加2}// 情况2: 前一个字符是 ')'，形如 "...))"else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {  // 检查是否形成嵌套结构// 获取匹配左括号之前的有效长度（如果存在）int prev = (i - dp[i - 1] - 2 >= 0) ? dp[i - dp[i - 1] - 2] : 0;dp[i] = dp[i - 1] + 2 + prev;  // 计算当前有效长度}// 更新最大长度if (dp[i] > maxLen) maxLen = dp[i];  // 如果当前值更大则更新maxLen}// s[i] == '(' 的情况，dp[i]保持0（因为以左括号结尾不可能是有效括号串的结尾）}free(dp); // 释放动态分配的内存，防止内存泄漏return maxLen;  // 返回找到的最大长度
}int main() {char input[1000]; // 输入缓冲区，最大999字符+1个结束符printf("请输入括号序列（只包含 '(' 和 ')'）：");  // 提示用户输入if (fgets(input, sizeof(input), stdin) == NULL) {  // 读取一行输入printf("输入错误！\n");  // 输入失败提示return 1;  // 非正常退出}// 移除可能的换行符：查找换行符位置并替换为字符串结束符input[strcspn(input, "\n")] = '\0';  // strcspn找到第一个换行符的位置// 验证输入是否只包含括号for (int i = 0; input[i] != '\0'; i++) {  // 遍历输入字符串if (input[i] != '(' && input[i] != ')') {  // 检查每个字符是否是括号printf("错误：输入只能包含 '(' 和 ')' 字符！\n");  // 错误提示return 1;  // 非正常退出}}int result = longestValidParentheses(input);  // 调用计算函数printf("最长有效括号子串长度：%d\n", result);  // 输出结果return 0;  // 正常退出程序
}

输出结果：

---

第三章：双子星对决——动态规划的阴阳辩证

📊 双题对比分析表

维度	打家劫舍	最长有效括号
问题类型	最优化问题	最长连续子串问题
状态定义	dp[i]: 前 i 间房的最大收益	dp[i]: 以 s[i] 结尾的有效长度
转移方程核心	当前偷或不偷（二选一）	当前字符与历史字符的匹配关系
空间复杂度	O(1)（滚动变量优化）	O(n)
难点突破	避免相邻选择	处理嵌套结构（如 (())）
哲学隐喻	贪心与克制的平衡	对称与连续的辩证统一

🔄 思维模型对比图

打家劫舍：线性决策链  
[房屋1] → [房屋2] → [房屋3]  
   │        │        │  
  偷/弃    偷/弃    偷/弃  

最长有效括号：时空回溯匹配  
... [  (  [已匹配子串]  )  ]  
      ↑        ↑        ↑  
    检查点  历史状态  当前字符

🌟 核心总结

1. 打家劫舍：决策是线性的，每个状态仅依赖前两个状态，体现“步步为营”的稳健。

2. 最长有效括号：决策是跳跃的，需回溯到历史子串起点，体现“时空折叠”的巧妙。

3. 动态规划的灵魂：

   • 状态定义是破局的关键（收益 vs 长度）。

   • 转移方程是逻辑的结晶（二选一 vs 匹配检查）。

   • 边界处理是稳健的基石（空数组、单字符等）。

---

博客结语

动态规划，是算法世界的“预言之书”。它教会我们：

小偷的智慧——真正的赢家不是贪得无厌者，而是懂得权衡取舍的谋士；
括号的密码——最复杂的迷宫，终将被对称的逻辑与历史的记忆破解。

无论你是算法新手还是江湖老手，这两个问题都将重塑你对“最优解”的认知。下次面对难题时，不妨自问：

“若是小偷，如何取舍？若是括号，何处匹配？”

---

📣 互动话题

如果给小偷增加“每隔两房必偷一次”的限制，如何修改状态方程？

括号问题能否用栈代替DP？各有何优劣？