题解 | #最长回文子序列#

package main

import "fmt"

func solution(str string) int {
	dp := make([][]int, len(str))
	for i := range dp {
		dp[i] = make([]int, len(str))
	}
	for row := len(str) - 1; row >= 0; row-- {
		dp[row][row] = 1
		for col := row + 1; col < len(str); col++ {
			//str[row] = str[col]
			if str[row] == str[col] {
				dp[row][col] = dp[row+1][col-1] + 2
			} else {
				dp[row][col] = max(dp[row+1][col], dp[row][col-1])
			}
		}
	}
	return dp[0][len(str)-1]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	//str := "abccsb" //结果4
	var str string 
	fmt.Scanln(&str)
	fmt.Println(solution(str))
}