ok

NoteXYX · NoteXYX · commit 6d328d0700ac · 2020-09-12T00:15:55.000+08:00
diff --git a/src/com/leetcode/Main516.java b/src/com/leetcode/Main516.java
@@ -0,0 +1,34 @@
+package com.leetcode;
+
+/**
+ * 516. 最长回文子序列
+ * 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
+ *
+ *  
+ *
+ * 示例 1:
+ * 输入:"bbbab"
+ * 输出:4
+ */
+public class Main516 {
+    public int longestPalindromeSubseq(String s) {
+        if (s == null || s.length() == 0) {
+            return 0;
+        }
+        int n = s.length();
+        int[][] dp = new int[n][n];
+        for (int i = 0; i < n; i++) {
+            dp[i][i] = 1;
+        }
+        for (int i = n-1; i >=0; i--) {
+            for (int j = i+1; j < n; j++) {
+                if (s.charAt(i) == s.charAt(j)) {
+                    dp[i][j] = dp[i+1][j-1] + 2;
+                } else {
+                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
+                }
+            }
+        }
+        return dp[0][n-1];
+    }
+}
