[数据结构与算法] Letcode动态规划专题-中级

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Letcode动态规划专题-中级 -> 正文阅读

[数据结构与算法]Letcode动态规划专题-中级

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。
在这里插入图片描述

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
在这里插入图片描述

‘’’
动态规划：
dp[i]表示i组括号的所有有效组合
dp[i] = “(dp[p]的所有有效组合)+【dp[q]的组合】”，其中 1 + p + q = i , p从0遍历到i-1, q则相应从i-1到0

/**
 * 动态规划
 * 从f(1),f(2),...,f(n-1)构建出f(n)
 *
 * 分析一个解的构成：必然从左括号开始，而这个开始的左括号必然对应着一个一个右括号，
 *     因此，任何一个解可以表示为 (A)B。
 * 令f(n) = (A)B  其中A和B是规模更小时问题的合法解，并且A、B可以为空，
 * 并且A中括号对数+B中括号对数之和为n-1
 *
 * 也就是说，可以从f(0),f(1),f(2),...,f(n-1构建出f(n),其中f0 = ""表示空解。
 */
public List<String> generateParenthesisDp(int n) {
    List<String>[] dp = new List[n+1];
    dp[0] = Arrays.asList("");

    for (int p = 1; p <= n; p++) {
        dp[p] = new ArrayList<>();
        for (int q = 0; q < p; q++) {
            for (String a : dp[q]) {
                for (String b : dp[p-q-1]) {
                    dp[p].add("("+a+")"+b);
                }
            }
        }
    }
    return dp[n];
}