Optimize the space complexity to O(n).

Work from bottom to top, from left to right, as is required. However, since the value at current cell(i,j) depends on cell(i+1,j-1), cell(i+1,j), and cell(i,j-1), based on the working direction, cell(i+1,j-1) needs to be saved.

class Solution { public: int longestPalindromeSubseq(string s) { if(s.empty()) return 0; vector<int> f(s.length(), 0); int prev = 0; for(int i=s.length()-1; i>=0; i--) { f[i] = 1; prev = 0; for(int j=i+1; j<s.length(); j++) { int save = f[j]; if(s[i]==s[j]) f[j] = prev+2; else f[j] = max(f[j-1],f[j]); prev = save; } } return f[s.length()-1]; } };