【算法日记】Day 3 一维动态规划基础

张开发
• 2026/4/3 17:27:10 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【算法日记】Day 3 一维动态规划基础
Abstract#动态规划#括号匹配#一维DP1. 题目题目LeetCode 32. 最长有效括号核心思路定义dp[i]表示必须以i结尾的最长有效括号长度。遇到(时显然有效括号不可能以(结尾所以该位置的dp[i]为 0遇到)时尝试通过dp[i]寻找上一个未匹配的(并连接之前的有效长度。复杂度时间复杂度 O(n)空间复杂度 O(n)2. 代码classSolution{public:intlongestValidParentheses(string s){if(s)return0;vectorintdp(s.size(),0);// 改为 s.size()索引从0开始intans0;for(inti1;is.size();i){if(s[i])){intprevi-dp[i-1]-1;// 与当前 ) 匹配的 ( 位置if(prev0s[prev](){dp[i]2dp[i-1](prev-10?dp[prev-1]:0);ansmax(ans,dp[i]);}}// s[i] ( 时 dp[i] 默认为0无需处理}returnans;}};3. 心得第一次尝试用栈一次遍历记录长度但遇到 ()() 时出错DP 通过状态转移完美处理嵌套和并列。状态定义错误定义dp[i]为“后 i 个字符中最长有效括号长度”但这样不易量化不同长度的有效括号串是否连续。正确做法是定义以 i 结尾的串最长有效长度保证了前后串的连接。索引计算越界prev i - dp[i-1] - 1必须检查prev 0同时prev-1也要检查是否大于等于 0。4. 相关题目LeetCode 639解码方法 II

更多文章