Submission #67625944

---

Source Code Expand

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

// longestPalindromicSubsequence は、与えられた文字列 S に対して、削除のみで構成可能な
// 最長の回文部分列の長さを返します。
// パラメータ:
//   - s string : 英小文字からなる入力文字列（長さ N）
// 戻り値:
//   - int : 最長の回文部分列の長さ
func longestPalindromicSubsequence(s string) int {
	n := len(s)

	// dp[i][j] := s[i..j] の最長回文部分列の長さ
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	// 長さ1の部分列は常に回文
	for i := 0; i < n; i++ {
		dp[i][i] = 1
	}

	// 長さ2以上の部分列についてのDP
	for length := 2; length <= n; length++ {
		for i := 0; i <= n-length; i++ {
			j := i + length - 1
			if s[i] == s[j] {
				if length == 2 {
					dp[i][j] = 2
				} else {
					dp[i][j] = dp[i+1][j-1] + 2
				}
			} else {
				if dp[i+1][j] > dp[i][j-1] {
					dp[i][j] = dp[i+1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
			}
		}
	}

	return dp[0][n-1]
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	// 入力 N は使用しないが、読み取りだけ行う
	_ = scanner.Text()

	scanner.Scan()
	s := strings.TrimSpace(scanner.Text())

	result := longestPalindromicSubsequence(s)
	fmt.Println(result)
}

Submission Info

Judge Result