LeetCode之Longest Palindromic Sub

问题：

方法：
算法的核心是动态规划，从短串推导到长串，当s[i] = s[j]时，dp[i][j] = dp[i+1][j-1] + 2；当
s[i] = s[j]时，dp[i][j] = maxOf(dp[i+1][j], dp[i][j-1])，类似斐波那契数列的演算过程，最后输出dp[0][s.lastIndex]即为最终结果。

具体实现：

class LongestPalindromicSubsequence {
    fun longestPalindromeSubseq(s: String): Int {
        if (s.isEmpty()) {
            return 0
        }
        val dp = Array(s.length) { Array(s.length) { 0 } }
        for (i in s.lastIndex downTo 0) {
            dp[i][i] = 1
            for (j in (i + 1)..s.lastIndex) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i+1][j-1] + 2
                } else {
                    dp[i][j] = maxOf(dp[i+1][j], dp[i][j-1])
                }
            }
        }
        return dp[0][s.lastIndex]
    }
}

fun main(args: Array<String>) {
    val input = "bbbab"
    val longestPalindromicSubsequence = LongestPalindromicSubsequence()
    println(longestPalindromicSubsequence.longestPalindromeSubseq(input))
}

有问题随时沟通

具体代码实现可以参考Github