前言

动态规划是通过以空间换时间的一种方式。
这种类型的题目就我个人而言不是特别的熟练，每次都需要刷些题找找感觉，因为它的关键是要找到初始状态和状态转移方程。

题目

一、22. 括号生成

// https://leetcode.cn/problems/generate-parentheses/solution/zui-jian-dan-yi-dong-de-dong-tai-gui-hua-bu-lun-da/
/*
    参考 lambda 的 go 版本
    1. 当我们要给出n个括号对组成的结果集 f(n)时，在这个结果中，所有字符串的第一个元素必然是 "("
    2. 那么必然有另一个与之匹配的右括号 ")"
    3. 那么还有 n-1 个括号对需要安放
    4. 这 n-1 个括号对中，可以有 j 个括号对位于上述这对括号的内部，那么剩余的 n-1-j 个括号对都在上述括号对右侧
    5. j的取值范围应该是 [0, n-1]
    6. 所以在计算f(n)时， 我们是需要知道 f(0), f(1), ... f(n-1)的结果的，因此需要用map保存dp过程中的每一个结果
*/
func generateParenthesis(n int) []string {
    return dp(n)[n]
}

func dp(n int) map[int][]string {
    if n == 0 {
        return map[int][]string{0: {""}}
    }
    if n == 1 {
        return map[int][]string{0: {""}, 1: {"()"}}
    }
    lastMap := dp(n - 1)
    var oneRes []string
    for i := 0; i < n; i++ {
        inners := lastMap[i]
        outers := lastMap[n-1-i]
        for _, inner := range inners {
            for _, outer := range outers {
                oneRes = append(oneRes, "("+inner+")"+outer)
            }
        }
    }
    lastMap[n] = oneRes
    return lastMap
}