It's well known that the longest palindromic subsequence (LPS) of a string s can be obtained by computing the longest common subsequence (LCS) of s and its reverse.

There may be multiple LCS's between a string and its reverse, some of which are palindromic and some of which are not.

For example the string "CABCA" and its reverse "ACBAC" have "ABC" and "ACA" as LCS's.

Here is the DP table:

    A C B A C

  0 0 0 0 0 0

C 0 0 1 1 1 1

A 0 1 1 1 2 2

B 0 1 1 2 2 2

C 0 1 2 2 2 3

A 0 1 2 2 3 3

I'm trying to understand why taking the topmost or bottommost path in the DP table will always yield a palindromic LCS. For example the topmost path here yields "CAC" and the bottommost path yields "ACA".

Can anyone explain this? Thank you in advance!