Leetcode: Longest Palindromic Subsequence

// https://code.dennyzhang.com/longest-palindromic-subsequence
// Basic Ideas: dynamic programming
//   optimal substructure:
//        Problem: the value of s[j...i]
//        if s[i] == s[j-1], f(s[j...i-1])+2
//        if s[i] != s[j-1], max(f(s[j...i-1]), f(s[j+1...i]))
//   Terminiation condition:
//        For s[j...i], when i==j, return 1
//
// Complexity: Time O(n^2), Space O(n^2)
func longestPalindromeSubseq(s string) int {
    dp := make([][]int, len(s))
    for i, _ := range dp {
        l := make([]int, len(s))
        for j, _ := range l {
            l[j] = 1
        }
        dp[i] = l
    }
    // dp[i][j]: s[j], s[j+1], s[j+2], ... s[i]
    for i:=1; i<len(s); i++ {
        for j:=i-1; j>=0; j-- {
            if s[i] == s[j] {
                // s[j], s[j+1...i-1], s[i]
                v := 2
                if j+1 <= i-1 {
                    v += dp[i-1][j+1]
                }
                dp[i][j] = v
            } else {
                // s[j+1...i]
                dp[i][j] = dp[i][j+1]
                if dp[i][j] < dp[i-1][j] {
                    // s[j...i-1]
                    dp[i][j] = dp[i-1][j]
                }
            }
        }
    }
    return dp[len(s)-1][0]
}