温州做网站的公司有哪些,网站开发找谁,wordpress多域名图标,做网站的技术盏647. 回文子串
dp含义#xff1a;dp如果是表示i-j的序列中回文子串的个数的话#xff0c;当新来一个后只能判定出来是整体的回文#xff0c;内部的无法判断#xff0c;所以用bool表示整体比较恰当。 递推公式#xff1a;由于i#xff0c;j是由i1,j-1决定的#xff0c;所…647. 回文子串
dp含义dp如果是表示i-j的序列中回文子串的个数的话当新来一个后只能判定出来是整体的回文内部的无法判断所以用bool表示整体比较恰当。 递推公式由于ij是由i1,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{resdp[i][j] true}else if dp[i 1][j - 1]{resdp[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 : i1; 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[i1][j])}}}return dp[0][len(s) - 1]
}
func max(a, b int)int{if a b{return b}else{return a}
}
