动态规划

// 本代码只是一种实现方式，仅供参考。
const rucksack = 4 // 背包大小
// 商品信息; 也可使用多个数组来分别存储商品信息的重量和价值
const goods = {
  guitar: {
    weight: 1,
    price: 1500
  },
  loudspeakerBox: {
    weight: 4,
    price: 3000
  },
  computer: {
    weight: 3,
    price: 2000
  }
}

/**
 * @description: 求放入背包的最大价值
 * @param {object} goods 商品信息
 * @param {number} capacity 背包容量
 * @return {number} 最大价值
 */
function putIn(goods, capacity) {
  const grid = new Array(Object.keys(goods).length)
  for (let i = 0; i < grid.length; i++) {
    grid[i] = new Array(capacity + 1).fill(0)
  }

  let index = 0
  for (let key in goods) {
    const weight = goods[key].weight // 当前选择商品的重量
    const goodsPrice = goods[key].price // 当前选择商品的价值
    for (let i = 1; i <= capacity; i++) {
      const preRest = index - 1 < 0 ? 0 : grid[index - 1][i - weight]
      const price = i >= weight ? goodsPrice + preRest : 0 // 放入该商品时的最大价值
      const prePrice = index - 1 < 0 ? 0 : grid[index - 1][i] // 不放该商品时的最大价值，即上一个此容量是的最大价值

      grid[index][i] = Math.max(price, prePrice) // 返回两种情况中价值最大的那个
    }
    index += 1
  }

  return grid[index- 1][capacity] // 返回最大价值
}

console.log(putIn(goods, rucksack))
// 输出：3500

var longestPalindrome = function (s) {
  const len = s.length
  // 因为长度小于 2，肯定是它本身
  if(len < 2) {
    return s
  }

  let maxLength = 1
  let start = 0
  // 划分一个 len * len 的表格
  // i j 分别表示子串的起始index 和 结束index，因此 i = j 必定是true，即一个字母的时候
  // 同时注意 i > j 是没有必要或者说是不合法的，因此这个表起始也就只填一半（以 i = j 划出分界线）
  const dp = new Array(len)
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len).fill(false)
    dp[i][i] = true
  }

  const charArr = s.split('')
  // 以 案例 babad 举例
  // L 代表子串的长度，比如 L = 2时需要验证， ba(01)、ab(12)、ba(23)、ad(34)
  // L = 1时没有必要验证，因为肯定都为true，并且上面已经处理
  for (let L = 2; L <= len; L++) {
    // 搜索并检验 s 中所有长度为L的子串
    for (let i = 0; i < len; i++) {
      // j 的 坐标（子串结束坐标）
      const j = L + i - 1

      // 超出右边界
      if(j >= len) break

      // 判断首尾字符是否一样
      if(charArr[i] !== charArr[j]) {
        dp[i][j] = false
      } else {
        // 如果子串长度小于等于3，只要首尾一样则肯定是回文子串，比如 bab
        // 如果这里理解不了，可以修改为 L <= 3
        // 如果长度大于三并且首尾一样，则去掉首尾判断是否是回文，比如 cbabc，已知bab是回文，那么cbabc肯定也是回文，因为首尾一样（dp[i+1][j-1] 就是这个意思）
        if(j - i < 3) {
          dp[i][j] = true
        } else {
          dp[i][j] = dp[i+1][j-1]
        }
      }

      // 记录最长回文长度 和 起始index
      if(dp[i][j] && L > maxLength) {
        maxLength = L
        start = i
      }
    }
  }

  return s.substring(start, start + maxLength)
}