公式化思考面试与机试中的动态规划类题目

公式化思考面试与机试中的动态规划类题目

  • 首先来一个题目:leetcode 32. 最长有效括号 问题:在一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。 示例: 输入:s = “)()())” 输出:4 解释:最长有效括号子串是 "()()" 范围: 0 <= s.length <= 3 * 10^4,其中s[i] 为 '(' 或 ')'。

动态规划思路

  • 初见动态规划可能会觉得无从入手,这里我们将动态规划分为三点:状态边界转移

状态

状态是指题目的条件能够组成的所有可能结果(比如括号的数量,每个括号是左括号还是右括号,括号的配对方式等)。 由于状态的描述方式许多,多数描述跟题目无关,这里给出一个固定句式

在 <满足问题的条件> 下,<问题的最佳答案> 就是状态。

此题中,代入句式得到:在<长度为s.length条件>下,《最长有效括号子串的数量《就是状态。 观察句式,句式中的变量只有长度,我们修改长度的表述,可以得到 <长度为1下>,《最长有效括号子串的数量》;<长度为2下>,《最长有效括号子串的数量》··· 等等表述。显然这些表述组合起来就是一个一维数组,通常习惯将此数组命名为dp正式地: ● 设在<长度为i条件下>,《最长有效括号子串的数量》就是dp[i]。 ● dp就是状态数组。


边界

固定句式中,代入确切的初始条件和终止条件,就是我们的边界,也是思考的起点和终点。

此题中的所有状态:<长度为1下>,《最长有效括号子串的数量》;<长度为2下>,《最长有效括号子串的数量》··· - 初始条件<长度为1下>的情况是容易计算的,显然<长度为1下>,《最长有效括号子串的数量》是0,那么得到dp[1]=0。 - 再有终止条件:在<长度为s.length条件>下,《最长有效括号子串的数量》就是dp[s.length],也就是题目的答案。

dp[1] = 0;
answer = dp[s.length];

转移

转移是由已知状态推导未知状态的过程。具体地讲: Q:什么是已知未知? A:在边界中,dp[1]=0就是已知状态,所求的答案dp[s.length]就是未知状态。

Q:转移是如何操作的? A:根据已知推未知,逐步推导。

示例:字符串 s = “)()())” 第一个字符为 ), 同时已知状态dp[1]=0就表示<长度为1下>,《最长有效括号子串的数量》是0。 加入第二个字符,则目前为)(,通过已知状态dp[1]和已知第二个字符(来推导未知状态dp[2]。 以此类推 加入第三个字符,目前为)(),通过已知状态dp[2]和已知第三个字符)来推导未知状态dp[3]。 正式地: 通过已知状态dp[i-1]和已知第i个字符s[i],来推导未知状态dp[i]。 简单表达:dp[i] = ( dp[i-1], s[i] )

Q:在计算 dp[i] 时,可以利用的信息有哪些? A:只可利用dp[i-1], s[i-1], s[i] 等邻近 i 的数据。

详细说明:若在计算dp[i]时,使用了 dp[1], dp[2]···,那么本次计算就要访问i-1个元素。 根据上述,计算i=1时访问0个元素,计算i=2时访问1个元素···,计算i=n时访问n-1个元素。 则计算完 i=n 时已经访问了 0+1+2+···+n-1 = n^2 ,即时间复杂度为O(n^2)。

诸如dp[i] = ( dp[i-1], s[i] )的式子,称为状态转移方程


解题步骤

1. 根据状态的固定句式,假设一个合理的状态,并说明答案和状态的关系。

2. 分类讨论每种状态对应的含义,写出状态转移方程。

3. 若第2步无法写出方程,则检查状态是否完备,并继续步骤1。

  • Q: 如何检查状态设置的正确性? a. 状态需要包含推导所需所有可能,不能有遗漏。 b. 状态i 和 之前的状态i-1, i-2···不能有交集。

本题示例:

  1. 使用上文设置的状态: dp[i]为在<长度为i条件下>,《最长有效括号子串的数量》,答案就是dp[n]。
  2. 思考状态转移方程,计算未知状态dp[i]时,已知dp[i-1]的值,对dp[i-1]的值分类讨论。 a. dp[i-1] 为0,则表示之前从未出现过有效的括号子串。 b. dp[i-1] 不为0,则表示之前出现过有效的括号子串,不知道在[1, i-1]的哪一段出现的。
  3. 这时我们发现使用dp[i-1]不大能够推算出dp[i],因为dp[i-1]和dp[i]都包含了可能 在[1, i-1]的某一段出现了《最长有效括号子串的数量》,违背状态的正确性。

hint: 常在固定句式中使用限定词“以i为结尾

  1. 使用上文设置的状态: dp[i]为在<长度为i条件下>,《以i为结尾的最长有效括号子串的数量》。答案就是dp[1]到dp[n]中的最大值。
  2. 思考状态转移方程,计算未知状态dp[i]时,已知dp[i-1]的值,对dp[i-1]的值分类讨论。 a. dp[i-1] 为0,则表示i-1位置的符号不能跟前面的括号匹配。 > 前i-1个字符可能是: * ( ,若此时s[i] = ')',则 dp[i] = 2。 > 也可能是: ( ) ),则 dp[i] = 0。 b. dp[i-1] 为k, k>0,则表示从i-1往前k个是恰好匹配的连续括号子串。 因为前面k个已经成功配对了,那么dp[i] 只能尝试跟 往前找第k+1个字符 配对,也就是 s[i-k]='(',且s[i]=')'时才能配对,dp[i] = dp[i-1] + 2。

可以得到一份代码:

class Solution {
public:
    int dp[30000 + 10], pos;
    int longestValidParentheses(string s) {
        // 因为c++下标从0开始, 这里填充一个字符在开头使得下标从1开始.
        s = "*" + s;
        // 边界
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= s.length(); i++)
        {
            dp[i] = 0;
            if (dp[i - 1] == 0)
            {
            // a.
                if (s[i - 1] == '(' && s[i] == ')')
                    dp[i] = 2;
            }
            else
            {
                // b.
                // pos就是往前找k+1个字符的位置
                // 比如 i=10,dp[i-1]=4,表示[6,7,8,9] 是匹配的子串,则 pos=5
                pos = i - dp[i - 1] - 1;
                if (s[pos] == '(' && s[i] == ')')
                    dp[i] = dp[i - 1] + 2;
            }
        }

        int ans = 0;
        for (int i = 1; i <= s.length(); i++)
            ans = max(ans, dp[i]);

        return ans;
    }
};

这里我们发现并不能解答此题,拿到错误数据为:")()())",错误答案为2。 我们发现是5号位置计算错误,根据状态的定义:《以i为结尾的最长有效括号子串的数量》,dp[5]应该为4。 - 那么我们需要检查状态转移方程,发现无论是a. 还是b.,在i位置发生匹配时,就要注意是否前面也有一个完整的匹配,形如 * * * √ √ √ √ ( ) ,dp[i]的值应该为本次匹配的结果加上 上一个紧挨着的连续合法括号串长度(上一个紧挨着的位置是pos=i-dp[i])。 - c. 第三条转移方程: 当i位置匹配成功(即dp[i]>0)时,也要加上 上一个紧挨着的连续合法括号串长度(即dp[pos])

// 代码如下
pos = i - dp[i];
if (dp[i])
    dp[i] += dp[pos]

// pos的值带进来简写
if (dp[i])
    dp[i] += dp[i - dp[i]]

最终代码

class Solution {
public:
    int dp[30000 + 10];
    int longestValidParentheses(string s) {
        // 因为c++下标从0开始, 这里填充一个字符在开头使得下标从1开始.
        s = "*" + s;
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= s.length(); i++)
        {
            dp[i] = 0;
            if (dp[i - 1] == 0)
            {
                if (s[i - 1] == '(' && s[i] == ')')
                    dp[i] = 2;
            }
            else
            {
                int pre_pos = i - dp[i - 1] - 1;
                if (s[pre_pos] == '(' && s[i] == ')')
                    dp[i] = dp[i - 1] + 2;
            }

            // c. 加这里
            if (dp[i])
            {
                dp[i] += dp[i - dp[i]];
            }
        }

        int ans = 0;
        for (int i = 1; i <= s.length(); i++)
            ans = max(ans, dp[i]);

        return ans;
    }
};

关于我们

欢迎关注公众号《奇迹狗狗》,很开心在这里能和你相遇~

我们会分享一些技术文章,包括但不限于游戏技术、云原生、ACM题解、基础编程知识等,如果能授人以渔,荣幸之至!

我们也会做一些有温度的产品、游戏,会陆续分享给大家,如果能博君一笑,再好不过!

产品列表: ★ WorkerHub小程序,信息均来自各个大厂员工爆料,可以查询各个公司/部门/岗位的工作做细、工作体验、工作评价等,供打工er找工作的时候参考,避雷卷王团队/天坑团队!

版权声明:
作者:奇迹狗狗
链接:https://jkboy.com/archives/17156.html
来源:随风的博客
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
海报
公式化思考面试与机试中的动态规划类题目
状态是指题目的条件能够组成的所有可能结果(比如括号的数量,每个括号是左括号还是右括号,括号的配对方式等)。 由于状态的描述方式许多,多数描述跟题目无关,这里给出...
<<上一篇
下一篇>>