Add C++ implementation

begeekmyfriend · begeekmyfriend · commit 84dd3f80f212 · 2021-02-17T23:18:51.000+08:00
Signed-off-by: begeekmyfriend &lt;begeekmyfriend@gmail.com&gt;
diff --git a/0516_longest_palindromic_subsequence/Makefile b/0516_longest_palindromic_subsequence/Makefile
@@ -0,0 +1,2 @@
+all:
+	gcc -O1 -o test lps.c
diff --git a/0516_longest_palindromic_subsequence/lps.c b/0516_longest_palindromic_subsequence/lps.c
@@ -0,0 +1,43 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+
+static inline int max(int a, int b)
+{
+    return a > b ? a : b;
+}
+
+int longestPalindromeSubseq(char * s)
+{
+    int i, j, k;
+    int len = strlen(s);
+    int **dp = malloc(len * sizeof(int *));
+    for (i = 0; i < len; i++) {
+        dp[i] = malloc(len * sizeof(int));
+        memset(dp[i], 0, len * sizeof(int));
+        dp[i][i] = 1;
+    }
+
+    for (k = 1; k < len; k++) {
+        for (i = 0; i < len - k; i++) {
+            j = i + k;
+            if (s[i] == s[j]) {
+                dp[i][j] = dp[i + 1][j - 1] + 2;
+            } else {
+                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
+            }
+        }
+    }
+    return dp[0][len - 1];
+}
+
+int main(int argc, char **argv)
+{
+    if (argc != 2) {
+        fprintf(stderr, "Usage: ./test s\n");
+        exit(-1);
+    }
+
+    printf("%d\n", longestPalindromeSubseq(argv[1]));
+    return 0;
+}
diff --git a/0516_longest_palindromic_subsequence/lps.cc b/0516_longest_palindromic_subsequence/lps.cc
@@ -0,0 +1,25 @@
+#include <bits/stdc++.h>
+
+using namespace std;
+
+class Solution {
+public:
+    int longestPalindromeSubseq(string s) {
+        int len = s.length();
+        vector<int> dp(len, 1);
+        // We have to use level traverse to reduce the dp table size
+        for (int i = len - 2; i >= 0; i--) {
+            int left_down = 0;
+            for (int j = i + 1; j < len; j++) {
+                int down = dp[j];
+                if (s[i] == s[j]) {
+                    dp[j] = left_down + 2;
+                } else {
+                    dp[j] = max(down, dp[j - 1]);
+                }
+                left_down = down;
+            }
+        }
+        return dp[len - 1];
+    }
+};
