{"size": 766, "ext": "js", "max_stars_repo_path": "leetcode/516.longest-palindromic-subsequence.js", "max_stars_repo_name": "iuiaoin/leetcode", "max_stars_repo_stars_event_min_datetime": null, "max_stars_repo_stars_event_max_datetime": null, "max_issues_repo_path": "leetcode/516.longest-palindromic-subsequence.js", "max_issues_repo_name": "iuiaoin/leetcode", "max_issues_repo_issues_event_min_datetime": null, "max_issues_repo_issues_event_max_datetime": null, "max_forks_repo_path": "leetcode/516.longest-palindromic-subsequence.js", "max_forks_repo_name": "iuiaoin/leetcode", "max_forks_repo_forks_event_min_datetime": null, "max_forks_repo_forks_event_max_datetime": null}
{"max_stars_count": null, "max_issues_count": null, "max_forks_count": null, "avg_line_length": 23.9375, "max_line_length": 117, "alphanum_fraction": 0.4751958225}
/*
 * @lc app=leetcode id=516 lang=javascript
 *
 * [516] Longest Palindromic Subsequence
 */
/**
 * @param {string} s
 * @return {number}
 */
/**
 * 思路：
 * state: dp[i][j]表示s.slice(i, j)的最长回文串
 * state transition: 若s[i] == s[j], dp[i][j] = dp[i + 1][j - 1] + 2, 否则dp[i][j] = max{dp[i + 1][j], dp[[i],[j - 1]]};
 * initialization: dp[i][i] = 1
 */
var longestPalindromeSubseq = function(s) {
  let len = s.length;
  let dp = new Array(len).fill(null).map(v => new Array(len).fill(0));
  for(let i = len - 1; i >= 0; i--) {
    dp[i][i] = 1;
    for(let j = i + 1; j < len; j++) {
      if(s[i] === s[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][len - 1];
};

