js动态规划
动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，把原问题分解为相对简单的子问题
动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。
动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。
使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。
1.给一个字符串 s，找到 s 中最长的 回文子串。
中心扩展法
function longestPalindrome(s) { if (s.length < 2) return s; let start = 0, maxLength = 1; // 辅助函数，用于通过中心向两边扩展检查回文 const expandAroundCenter = (left, right) => { while (left >= 0 && right < s.length && s[left] === s[right]) { // 更新最长回文的边界 if (right - left + 1 > maxLength) { start = left; maxLength = right - left + 1; } // 向两边扩展 left--; right++; } }; // 遍历字符串的每一个字符作为中心 for (let i = 0; i < s.length - 1; i++) { // 奇数长度的回文 expandAroundCenter(i, i); // 偶数长度的回文 expandAroundCenter(i, i + 1); } return s.substring(start, start + maxLength);
} console.log(longestPalindrome("babad")); // 输出: "bab"
console.log(longestPalindrome("cbbd")); // 输出: "bb"动态规划法
function longestPalindrome(s) { if (s.length < 2) return s; let start = 0, maxLength = 1; const n = s.length; // 初始化dp数组，长度为n的字符串需要n*n的二维数组 const dp = Array.from({ length: n }, () => Array(n).fill(false)); // 所有长度为1的子串都是回文 for (let i = 0; i < n; i++) { dp[i][i] = true; } // s.length = 2 for (let i = 0; i < n - 1; i++) { if (s[i] === s[i + 1]) { dp[i][i + 1] = true; start = i; maxLength = 2; } } // s.length > 2 for (let len = 3; len <= n; len++) { for (let i = 0; i <= n - len; i++) { const j = i + len - 1; if (s[i] === s[j] && dp[i + 1][j - 1]) { dp[i][j] = true; start = i; maxLength = len; } } } return s.substring(start, start + maxLength);
}