动态规划（Dynamic Programming，简称 DP）是一种将复杂问题分解为更小子问题、并利用子问题的解构建原问题解的方法，特别适用于具有重叠子问题和最优子结构的问题。根据实现方式的不同，常见的有以下几种：

注

动态规划和递归的区别：

递归是实现动态规划的常用方式，但动态规划不一定是递归。

实现方式

记忆化搜索（自顶向下）

也叫 递归 + 记忆化（Memoization），通过递归求解子问题，并用缓存记录已计算结果，避免重复计算。

✅ 特点：

• 思路清晰、接近数学定义；
• 代码简洁；
• 适合子问题不密集的场景。

📦 示例代码：斐波那契数列

// 纯递归
// 会有重复计算，时间复杂度 O(2^n)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// 递归 + 记忆化搜索
// 时间复杂度 O(n)，空间复杂度 O(n)
function fib(n, memo = {}) {
  if (n <= 1) return n;
  // 记忆化搜索：如果 memo 中存在 n，则直接返回 memo[n]
  if (memo[n]) return memo[n];

  // 递归计算 n 的值，并将其存储在 memo 中
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);

  // 返回当前的 n 的值
  return memo[n];
}

// 递归 + 记忆化搜索(把 memo 放到函数里面)
function fib(n) {
  const memo = {};

  // 递归函数
  function dfs(k) {
    if (k <= 1) return k;
    if (memo[k]) return memo[k];
    memo[k] = dfs(k - 1) + dfs(k - 2);
    return memo[k];
  }

  return dfs(n);
}

---

递推（自底向上）

也称 表格法 / 循环法，先从最小子问题出发，一步步推导出最终解。

✅ 特点：

• 时间效率高；
• 不依赖递归栈；
• 更适合优化空间。

📦 示例代码：斐波那契数列

function fib(n) {
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

---

状态压缩（空间优化）

对于只依赖前几个状态的 DP 问题，可以压缩空间，减少数组使用，优化内存。

✅ 特点：

• 空间复杂度大幅下降；
• 运算更快；
• 适合线性 DP、固定步长转移的问题。

📦 示例代码：斐波那契数列

function fib(n) {
  if (n <= 1) return n;
  let a = 0;
  let b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

---

实现方式对比

实现方式	优点	缺点	适用场景
记忆化搜索	简单易写，接近数学定义	有递归栈，空间可能较大	树状结构、子问题不密集
递推（表格法）	性能稳定、结构清晰	需要预先设计好状态和顺序	通用型 DP 问题
状态压缩	节省空间，速度更快	可读性差，逻辑更难理解	状态依赖少（如前一项）的场景

---

例题

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？

解题思路

1. 确定状态转移方程

   • 状态：dp[i][j] 表示机器人到达 (i, j) 位置的路径数（重点在于找到不同的 i 和 j 之间的关系）
   • 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

2. 确定特殊状态

   • i===0 或 j===0 时，dp[i][j] = 1

3. 确定边界条件

   • i < 0 或 j < 0 时，dp[i][j] = 0

代码实现

// 方法一：使用二维数组
function uniquePaths(m, n) {
  // 1. 初始化二维 dp 数组
  const dp = Array.from({ length: m }, () => Array(n).fill(0));

  // 2. 初始化边界条件
  for (let i = 0; i < m; i++) {
    dp[i][0] = 1;
  }
  for (let j = 0; j < n; j++) {
    dp[0][j] = 1;
  }

  // 3. 状态转移
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }

  // 4. 返回结果
  return dp[m - 1][n - 1];
}

// 方法二：使用一维数组
function uniquePaths2(m, n) {
  const dp = [];

  for (let i = 0; i < m; i++) {
    dp.push([]);
    for (let j = 0; j < n; j++) {
      if (i === 0 || j === 0) {
        dp[i][j] = 1;
      } else {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
  }

  return dp[m - 1][n - 1];
}

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

解题思路

• dp[i][j] = true 表示从 s[i] 到 s[j] 这一段是回文串。如果是回文，dp[i][j] = true，否则，dp[i][j] = false
• dp[i][j] === dp[j][i]
• 状态转移：如果 s[i] === s[j]，并且：
  • j - i < 3（即长度为 2 或 3），只要两端相等就是回文
  • 否则，dp[i][j] = dp[i+1][j-1]，也就是看去掉两端后中间是不是回文
• 先把对角线（单个字符）都设为 true
• 然后填充右上三角，判断每个区间是不是回文

i \ j	0	1	2	3	4
0	true
1	-	true
2	-	-	true
3	-	-	-	true
4	-	-	-	-	true

代码实现

动态规划法

function longestPalindrome(s) {
  const n = s.length;
  if (n < 2) return s;

  // 初始化 dp 表
  const dp = Array.from({ length: n }, () => Array(n).fill(false));
  let start = 0; // 记录最长回文子串的起始位置
  let maxLen = 1; // 记录最长回文子串的长度

  // 单个字符都是回文
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  // 填充 dp 表，从左上角开始，向右下角填充，填充上半部分
  for (let j = 1; j < n; j++) {
    for (let i = 0; i < j; i++) {
      if (s[i] === s[j]) {
        // 边界条件
        if (j - i < 3) {
          dp[i][j] = true; // 子串长度为 2 或 3，只需判断两端相等
        } else {
          dp[i][j] = dp[i + 1][j - 1]; // 状态转移
        }
      } else {
        dp[i][j] = false; // 不相等，直接设为 false
      }

      // 如果是回文并且长度更长，更新结果
      if (dp[i][j] && j - i + 1 > maxLen) {
        maxLen = j - i + 1;
        start = i;
      }
    }
  }

  return s.substring(start, start + maxLen);
}

中心扩展法

function longestPalindrome(s) {
  const n = s.length;
  if (n < 2) return s;

  let res = ""; // 初始化结果字符串为空

  // 定义一个函数，用于查找回文串
  const palindrome = (left, right) => {
    // 当左指针不越界，右指针不越界，且左右字符相等时，扩展指针
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--; // 左指针向左扩展
      right++; // 右指针向右扩展
    }
    // 返回回文子串 (左右指针已经越界或不相等了)
    return s.slice(left + 1, right);
  };

  // 遍历字符串的每个字符，以每个字符为中心，向两边扩展，找到最长的回文子串
  // 每个字符串都可能成为最长回文字串的中心
  for (let i = 0; i < s.length; i++) {
    // 查找以当前字符为中心的回文子串（奇数长度）
    const s1 = palindrome(i, i);
    // 查找以当前字符和下一个字符为中心的回文子串（偶数长度）
    const s2 = palindrome(i, i + 1);

    // 每次循环更新结果为较长的回文子串
    // 每次从 res, s1, s2 三个字符串中取最长的字符串
    res = res.length > s1.length ? res : s1;
    res = res.length > s2.length ? res : s2;
  }

  // 返回最长的回文子串
  return res;
}

双指针法

function longestPalindrome(s) {
  if (s.length < 2) return s;

  // 当前找到的最长回文串的起止位置
  let left = 0;
  let right = 0;

  // 以 m 和 n 为中心，向两边扩展，找到以这两个下标为中心的最长回文子串
  const palindrom = (m, n) => {
    while (m >= 0 && n <= s.length && s[m] === s[n]) {
      m--;
      n++;
    }

    // 循环结束后，实际的回文串区间是 [m+1, n-1]
    // 如果新找到的回文串长度比当前记录的还长，就更新 left 和 right
    if (n - m - 1 > right - left + 1) {
      left = m + 1;
      right = n - 1;
    }
  };

  // 遍历字符串的每个字符，分别以单个字符（奇数长度回文）和相邻两个字符（偶数长度回文）为中心，调用 palindrom
  for (let i = 0; i < s.length; i++) {
    palindrom(i, i);
    palindrom(i, i + 1);
  }

  return s.slice(left, right + 1);
};