美文网首页
!回溯算法思路

!回溯算法思路

作者: monkeyfly36 | 来源:发表于2024-03-14 15:47 被阅读0次

    回溯算法,死抓三点
    选择
    在这里,每次最多两个选择,选左括号或右括号,“选择”会展开出一棵解的空间树。
    用 DFS 遍历这棵树,找出所有的解,这个过程叫回溯。
    约束条件
    即,什么情况下可以选左括号,什么情况下可以选右括号。
    利用约束做“剪枝”,即,去掉不会产生解的选项,即,剪去不会通往合法解的分支。
    比如(),现在左右括号各剩一个,再选)就成了()),不能让这个错的选择成为选项(不落入递归):
    目标
    构建出一个用尽 n 对括号的合法括号串。
    意味着,当构建的长度达到 2*n,就可以结束递归(不用继续选了)。

    相关文章

      网友评论

          本文标题:!回溯算法思路

          本文链接:https://www.haomeiwen.com/subject/yjjwzdtx.html