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

奇迹狗狗 • 2023-01-02 • 云技术社区 • 276 阅读

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

首先来一个题目：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···不能有交集。

本题示例：

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

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

使用上文设置的状态: dp[i]为在<长度为i条件下>，《以i为结尾的最长有效括号子串的数量》。答案就是dp[1]到dp[n]中的最大值。
思考状态转移方程，计算未知状态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;
    }
};