leetcode-go/leetcode/medium/516.longest-palindromic-subsequence.go

func longestPalindromeSubseq(s string) int {
	n := len(s)
	if n < 2 {
		return n
	}
	runes := []rune(s)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
		dp[i][i] = 1
	}
	// dp[i][j], len of LPS of s[i:j+1]
	// dp[i][j] = max(dp[i][j], dp[i+1][j-1]+2), if s[i] == s[j]
	// dp[i][j] = max(dp[i+1][j], dp[i][j-1]), if s[i] != s[j]
	for l := 1; l < n; l++ {
		for i := 0; i+l < n; i++ {
			if runes[i] == runes[i+l] {
				dp[i][i+l] = maxInt(dp[i][i+l], dp[i+1][i+l-1]+2)
				// If j-1 < i+1, dp[i][j] = 0
			} else {
				dp[i][i+l] = maxInt(dp[i+1][i+l], dp[i][i+l-1])
			}
		}
	}
	return dp[0][n-1]
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}