2021-08-04：给定一个字符串str，当然可以生成很多子序列。返回有多少个子序列是回文子序列，空序列不算回文。比如，str

福大大架构师每日一题

发布于 2021-08-06 02:33:34

34800

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2021-08-04：给定一个字符串str，当然可以生成很多子序列。返回有多少个子序列是回文子序列，空序列不算回文。比如，str = “aba”，回文子序列：{a}、{a}、 {a,a}、 {b}、{a,b,a}，返回5。

福大大答案2021-08-04：

范围尝试模型。

dp[L][R]。

4种情况。

1.不包含L，不包含R。

2.不包含L，包含R。

3.包含L，不包含R。

4.包含L，包含R。

dp[L][R]依赖dp[L+1][R]，dp[L][R-1]，dp[L+1][R-1]。

时间复杂度：O(N**2)。

空间复杂度：O(N**2)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    ret := ways2("acac")
    fmt.Println(ret)
}

func ways2(str string) int {
    if len(str) == 0 {
        return 0
    }
    n := len(str)
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
    }
    for i := 0; i < n; i++ {
        dp[i][i] = 1
    }
    for i := 0; i < n-1; i++ {
        if str[i] == str[i+1] {
            dp[i][i+1] = 3
        } else {
            dp[i][i+1] = 2
        }
    }
    for L := n - 3; L >= 0; L-- {
        for R := L + 2; R < n; R++ {
            dp[L][R] = dp[L+1][R] + dp[L][R-1] - dp[L+1][R-1]
            if str[L] == str[R] {
                dp[L][R] += dp[L+1][R-1] + 1
            }
        }
    }
    return dp[0][n-1]
}