day 49 | 647. 回文子串 ● 516.最长回文子序列

647. 回文子串

dp含义：dp如果是表示i-j的序列中回文子串的个数的话，当新来一个后只能判定出来是整体的回文，内部的无法判断，所以用bool表示整体比较恰当。
递推公式：由于i，j是由i+1,j-1决定的，所以相当于是从右下开始遍历
初值：开始时必然都是false

func countSubstrings(s string) int {dp := make([][]bool, len(s) + 1)for i := 0; i < len(dp);i++{dp[i] = make([]bool, len(s) + 1)}res := 0for i := len(s); i >= 1; i--{for j := i; j <= len(s); j++{if s[i - 1] == s[j - 1]{if j - i <= 1{res++dp[i][j] = true}else if dp[i + 1][j - 1]{res++dp[i][j] = true}}}}return res
}

516.最长回文子序列

dp数组（dp table）以及下标的含义
dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

func longestPalindromeSubseq(s string) int {dp := make([][]int, len(s))for i := 0; i < len(s); i++{dp[i] = make([]int, len(s))dp[i][i] = 1}for i := len(s) - 1; i >= 0; i--{for j := i+1; j < len(s); j++{if s[i] == s[j]{dp[i][j] = dp[i + 1][j - 1] + 2}else{dp[i][j] = max(dp[i][j - 1], dp[i+1][j])}}}return dp[0][len(s) - 1]
}
func max(a, b int)int{if a < b{return b}else{return a}
}