【LeetCode选讲·第十一期】「括号生成」(DFS搜索,DP动态规划)

【LeetCode选讲·第十一期】「括号生成」(DFS搜索,DP动态规划)这是【LeetCode选讲·第十一期】。本次主要带来「括号生成」的题解及解答代码。主要涉及的知识点有”DFS深度优先搜索”,”剪枝优化”,”DP动态规划”。

T22 括号生成

题目链接:leetcode-cn.com/problems/ge…

思路一:DFS搜索

朴素解法

这是一道典型的「DFS搜索」题目,与之前我们学习过的「电话号码的字母组合」类似,但这里我们会分析得更细致一些。

对于此类题目,为了便于入手,我们不妨先不考虑任何优化,只考虑如下几个问题:

  1. 搜索的起点在哪里?
  2. 如何进行搜索?
  3. 每一个搜索节点下有几条分支?
  4. 如何判断一条搜索路径是否结束?

对于问题(1),由题意我们知道,想要形成闭合的括号组合,最左侧的括号必须是(,这就是我们的起点。

对于问题(2),我们只需要从最左侧出发,逐位搜索(实际上是枚举)可能的所有情况即可。

对于问题(3),由于我们这里先不考虑优化,因此每个搜索节点下只有两条分支(即两种可能性):()

对于问题(4),根据本题题意我们知道,如果要结束一条搜索路径,无非是碰到了两种情况:①发现搜索到了正确答案;②发现再往下搜索不可能得到正确答案。

我们先考虑前者。

为了表述方便,我们不妨记已搜索到的(数量为leftNum,已搜索到的)rightNum

很显然,只有当leftNum == rightNum == n时,才说明已经找到了正确的答案。

“等等!仅仅保证左右括号数量相等还不够,还需要保证它们能够一一闭合才对啊!”,如果你现在心中有这个疑惑,非常棒。但请不要着急,先让我们分析后者。

什么时候再往下不可能得到正确答案呢?

首先,题目已经规定了答案中括号对的个数n,也就是说,倘若我们对每个答案枚举的字符个数超过n * 2(下记作totalNum)却发现其不是正确答案,那么该路径必然需要结束。

其次,为了使得所有的括号对都有闭合的机会,必须保证搜索过程中始终有leftNum ≥ rightNum

这个条件稍稍有点难度,如果有同学想不明白的话,不妨用「反证法」:

假设leftNum < rightNum,表明已搜索到的左侧区域必定有多余的)存在,而此时无论我们如何在右侧区域添加括号(即继续往下搜索),都不可能使前面多余的)闭合。因此此时搜索到的结果肯定不是正确答案!

现在相信你已经解开了刚才的疑惑。是的,我们只要在搜索的中途将括号无法闭合的情况予以排除,就不需要在校验最终正确答案的时候考虑这个问题了!

现在我们已经分析清楚了这四个问题,下面直接运用我们的老朋友「递归」来实现「DFS搜索」就行了。由于代码比较简单,这里不再仔细讲解。如果你是初次接触此类题目的同学,请尝试找一找刚才的四个问题分别对应代码的哪一部分。

代码如下:

function generateParenthesis(n) {
    const ansArr = [];
    dfs(n * 2, 1, 0, '(', ansArr);
    return ansArr;
}
function dfs(totalNum, leftNum, rightNum, ans, ansArr) {
    if (totalNum === leftNum + rightNum) {
        leftNum === rightNum && ansArr.push(ans);
    }
    else if (leftNum >= rightNum) {
        dfs(totalNum, leftNum + 1, rightNum, ans + '(', ansArr);
        dfs(totalNum, leftNum, rightNum + 1, ans + ')', ansArr);
    }
}

剪枝优化

我们刚才已经编写出了完全不带任何优化的版本,下面我们尝试对其进行「剪枝优化」。

什么是「剪枝优化」呢,从字面上理解,就是在搜索的过程中及时发现并”剪去”搜索树上不可能抵达正确答案的”枝条”。

换句话说,就是我们需要在搜索过程中对一些具体情况进行研判,使得我们尽可能走可能抵达正确答案的搜索路径,规避不可能抵达正确答案的路径。

首先是我们很容易想到的两种情况:

  • leftNum = rightNum时,答案中下一个字符必须是(
  • leftNum + rightNum = totalNum - 1时,答案中下一个字符必须是).

还要其他可以进行剪枝的情况吗?

答案是肯定的。别忘了我们之前分析过,如果要找到正确答案,必须保证搜索过程中不等式leftNum ≥ rightNum始终成立。那么反过来说,如果走某一条路径会打破这个不等式,那么搜这个路径一定不会得到正确答案!

根据上面的分析,我们优化的代码如下:

function generateParenthesis(n) {
    const ansArr = [];
    //注意:现在这里若写dfs(n * 2, 0, 0, '', ansArr);也是可以的
    //思考:为什么?
    dfs(n * 2, 1, 0, '(', ansArr);
    return ansArr;
}
function dfs(totalNum, leftNum, rightNum, ans, ansArr) {
    if (totalNum === leftNum + rightNum) {
        leftNum === rightNum && ansArr.push(ans);
    }
    //思考:为什么先前代码中的条件leftNum >= rightNum已不再需要?
    else {
        if (leftNum === rightNum) {
            dfs(totalNum, leftNum + 1, rightNum, ans + '(', ansArr);
        } else if (leftNum + rightNum === totalNum - 1) {
            dfs(totalNum, leftNum, rightNum + 1, ans + ')', ansArr);
        } else {
            leftNum + 1 >= rightNum && dfs(totalNum, leftNum + 1, rightNum, ans + '(', ansArr);
            leftNum >= rightNum + 1 && dfs(totalNum, leftNum, rightNum + 1, ans + ')', ansArr);
        }
    }
}

拓展:从代数角度理解

下面我们来提一下如何从代数角度来理解本题中「DFS搜索」的实现。

我们可以记出现一个(为得+1分,出现一个)为得-1分。那么对于符合题意的括号组合,都有:

  • 当搜索到最终结果时,有总分score = 0,即leftNum = rightNum. 且搜索深度deep = n * 2,即leftNum + rightNum = totalNum
  • 在搜索过程中,总分始终满足0 ≤ score ≤ n,即leftNum ≥ rightNumleftNum ≤ n

这两条结论与我们上文中对题意的分析是完全吻合的。

代码如下:

function generateParenthesis(n) {
    const ansArr = [];
    dfs(n * 2, 1, 1, '(', ansArr);
    return ansArr;
}
function dfs(maxDeep, deep, score, ans, ansArr) {
    if (deep === maxDeep) {
        score === 0 && ansArr.push(ans);
    } else {
        if (score === 0) {
            dfs(maxDeep, deep + 1, score + 1, ans + '(', ansArr);
        } else if (deep === maxDeep - 1) {
            dfs(maxDeep, deep + 1, score - 1, ans + ')', ansArr);
        } else {
            score + 1 <= maxDeep/2 && dfs(maxDeep, deep + 1, score + 1, ans + '(', ansArr);
            score - 1 >= 0 && dfs(maxDeep, deep + 1, score - 1, ans + ')', ansArr);
        }
    }
}

思路二:DP动态规划

从观察开始

下面我们思考一个问题:这道题可以用「动态规划」进行解答吗?

我们知道,如果一道题可以用「动态规划」进行解答,那么题目中必须蕴含着某种递推关系

如果你还没有任何头绪的话,我们可以先来观察一下使用前面「DFS搜索」获得的几组正确答案:

1.png

请留意:是不是当n比较大时的答案,看上去像n比较小时的答案组装起来的

为了进一步发掘其中的规律,我们来举一个具体的例子分析一下。

比如当n = 4时的一个答案'(()())()'。为了更好地观察,我们拆开来看:'( ()() ) ()'

现在一切就很明显了,这个答案看上去应该是在一组新增加的括号内塞了n = 2时的一个答案()(),又再它的外面加了n = 1时的一组答案。我们知道1 + 2 + 1 = 4,这便是这个n = 4答案的由来!

递推关系

类似上面的例子还有很多。通过对它们的分析,我们寻找的递推关系也就呼之欲出了:

若规定dp[n]表示当括号对总数为n时的任意一个答案,

则有dp[n] = "(" + dp[p] + ")" + dp[q],其中p + q + 1 = n.

代码实现

利用递推关系,我们只需逐一计算从1n - 1的所有正确答案,便能够得到括号对为n时的答案——因为对每一个dp[n]中的答案,它都是由前面的dp[n - 1]中的答案递推(也就是所谓的”组装”)出来的!

代码如下:

function generateParenthesis(n) {
    /* 初始化dp数组 */
    const dp = [['']];
    for(let i = 1; i <= n; i++) dp[i] = [];
    /* 动归核心部分 */
    for(let curN = 1; curN <= n; curN++) {
        for(let p = 0; p < curN; p++) {
            let q = curN - p - 1;
            //由于dp[n]中可能包含了多个答案,
            //所以别忘了需要对其逐个进行遍历。
            for(let inside of dp[p]) {
                for(let outside of dp[q]) {
                    dp[curN].push("(" + inside + ")" + outside);
                }
            }
        }
    }
    /* 返回所求结果 */
    return dp[n];
}

写在文末

我是来自在校学生编程兴趣小组江南游戏开发社的PAK向日葵,我们目前正在致力于开发自研的非营利性网页端同人游戏《植物大战僵尸:旅行》,以锻炼我们的前端应用开发能力。

我们诚挚邀请您体验我们的这款优秀作品,如果您喜欢TA的话,欢迎向您的同事和朋友推荐。如果您有技术方面的问题希望与我们探讨,欢迎直接与我联系。您的支持是我们最大的动力!

QQ图片20220701165008.png

今天的文章【LeetCode选讲·第十一期】「括号生成」(DFS搜索,DP动态规划)分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/21520.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注