动态规划

• 最优子结构
• 边界
• 状态转移方程

回文子串

题目编号：647
回文子串

const countSubstrings = (s) => {
  let count = 0;
  const len = s.length;

  const dp = new Array(len);
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len).fill(false);
  }

  for (let j = 0; j < len; j++) {
    for (let i = 0; i <= j; i++) {
      if (i == j) { // 单个字符
        dp[i][j] = true;
        count++;
      } else if (j - i == 1 && s[i] == s[j]) { // 两个字符 
        dp[i][j] = true;
        count++;
      } else if (j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]) { // 多于两个字符
        dp[i][j] = true;
        count++;
      }
    }
  }
  return count;
};

跳跃游戏

题目编号：55
跳跃游戏
其实这题很简单，使用贪心算法倒推即可。但是潜意识觉得不可行，自己又没有弄几个测试用例去测，下次应该避免这样的情况。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
  if (nums.length <= 1) {
    return true;
  }

  let result = false
  let numsLen = nums.length;
  let distance = 1;

  for (i = numsLen - 2; i >= 0; i--) {
    if (nums[i] >= distance) {
      distance = 1;
      if (i === 0) result = true;
    } else {
      distance++;
    }
  }

  return result;
};