"""
Exercise 2: Longest Palindromic Subsequence (LeetCode 516)

Return the length of the longest palindromic SUBSEQUENCE (gaps allowed).
dp[i][j] = dp[i+1][j-1] + 2 if s[i] == s[j] else max(dp[i+1][j], dp[i][j-1]).
"""

def longest_palindrome_subseq(s):
    # TODO
    return 0


# --- self-check: do not modify below this line ---
a, b, c = longest_palindrome_subseq("bbbab"), longest_palindrome_subseq("cbbd"), longest_palindrome_subseq("a")
print(a, b, c)
print("PASS" if (a, b, c) == (4, 2, 1) else "FAIL")