总结了回溯算法与动态规划的核心知识点及 Java 实现。回溯部分涵盖组合、排列、子集、切割、棋盘五大场景，强调 startIndex 与 used 数组的区别、剪枝优化及去重技巧。动态规划部分详解线性 DP、背包问题（01/完全/分组）、子序列/子串 DP、区间 DP、树形 DP 及状态压缩 DP，重点讲解状态定义、转移方程、初始条件、遍历顺序及空间优化。文章提供通用代码模板与高频 LeetCode 例题，适合后端面试准备。
回溯算法是后端面试中等题核心考察点（占比 60%+），本质是'深度优先搜索（DFS）+ 状态回退'的暴力搜索优化，核心解决'多阶段决策'类问题（组合、排列、子集、切割、棋盘）。
回溯算法 = 递归（深度优先遍历） + 状态回退（撤销选择），本质是'暴力枚举所有可能的决策路径'：
| 要素 | 含义 | Java 实现方式 |
|---|---|---|
| 路径 | 已做出的选择（如组合问题中已选的数字、N 皇后中已放皇后的位置） | List<Integer> path、StringBuilder |
| 选择列表 | 当前阶段可选择的选项（如组合问题中未选的数字、棋盘问题中可放皇后的列） | 数组/集合、boolean[] used（去重） |
| 结束条件 | 到达决策树底部，需记录结果（如组合长度达标、棋盘遍历完成） | 路径长度==目标长度、索引越界等 |
path.remove(path.size()-1)），否则会污染其他路径；boolean[] used（标记元素是否已选，避免重复选同一元素）；used 数组（跳过同一层重复元素）；res.add(new ArrayList<>(path))），而非直接 add(path)（引用传递会导致结果集被后续修改）。回溯 90% 的高频题可归为 5 类场景，每类场景都有'通用模板 + 专属剪枝/去重技巧'，二刷需逐个固化。
考察'无顺序的元素选择'（如选 [1,2] 和 [2,1] 视为同一组合），后端面试中等题高频（如组合总和、电话号码的字母组合）。
i>startIndex && nums[i]==nums[i-1] && !used[i-1]）。res.add(new ArrayList<>(path))，否则结果集所有元素指向同一 path；sum + nums[i] > target 则 break（而非 continue），因为数组已排序，后续元素更大。考察'有顺序的元素选择'（如 [1,2] 和 [2,1] 视为不同排列），后端面试中常与'去重'结合考察（有重复元素的排列）。
boolean[] used 数组标记元素是否已选，避免同一路径重复选；used[i]==true）；i>0 && nums[i]==nums[i-1] && !used[i-1]）；used[i]=true，将 nums[i] 加入 path；used[i]=false，从 path 移除 nums[i]；!used[i-1]（同一层重复）而非 used[i-1]（同一路径重复），前者跳过同一层重复，后者跳过同一路径重复（会漏解）；nums[i]==nums[i-1] 判断，必须先排序；startIndex 控顺序，选过的元素后面不再选，结果是集合；used 数组控已选，选过的元素同一路径不再选，结果是序列。其实可以再抽象一层，因为很多题目不会直接告诉你是组合还是排序：顺序层面：考虑顺序 used，不考虑顺序用 offset 有重复元素的去重：排序是前提，考虑顺序那么去重的时候除了与前面一个元素相同，还要是当前层的元素
✔ 核心定义与目标差异
| 维度 | 组合问题 | 排列问题 |
|---|---|---|
| 核心本质 | 从 n 个元素中选 k 个元素，不考虑顺序 | 从 n 个元素中选 k 个元素，考虑顺序 |
| 结果特征 | [1,2] 和 [2,1] 视为同一个组合，只保留一个 | [1,2] 和 [2,1] 视为两个不同排列，都需要记录 |
| 核心目标 | 找出所有满足条件的'元素集合'（无顺序） | 找出所有满足条件的'元素序列'（有顺序） |
| 举例 | 从 [1,2,3] 选 2 个元素：[[1,2],[1,3],[2,3]] | 从 [1,2,3] 选 2 个元素：[[1,2],[2,1],[1,3],[3,1],[2,3],[3,2]] |
✔ 解题关键方法差异（回溯核心逻辑）
这是二者最核心的区别，直接决定代码的参数设计和遍历逻辑。
| 解题关键 | 组合问题 | 排列问题 |
|---|---|---|
| 控制顺序的核心手段 | startIndex 起始索引：限制下一层递归只能从当前元素的下一个位置开始选，避免重复组合 | used[] 标记数组：标记元素是否被选中，确保同一元素不会在同一路径中重复出现，同时允许从任意未选元素开始选 |
| 递归参数 | 必须传入 startIndex，无需 used 数组 | 必须传入 used 数组，无需 startIndex |
| 遍历范围 | for (int i = startIndex; i < n; i++)：从 startIndex 开始，保证顺序 | for (int i = 0; i < n; i++)：从 0 开始遍历所有元素，通过 used 过滤已选元素 |
| 回溯的核心目的 | 用 startIndex 规避顺序重复，无需去重标记 | 用 used 标记元素的选中状态，递归后恢复状态（used[i] = false） |
✔ 有重复元素时的去重逻辑差异
当原数组包含重复元素时（如 [1,1,2]），二者的去重策略都需要先排序，但去重条件不同，核心是区分'同一层重复'和'同一路径重复'。
理解：重复元素的去重都是针对同一层的元素。组合问题中，因为存在偏移量，所以 offset 右边的元素都是没有被选取的（保证了顺序性），所以去重的时候只需要保证在当层中与前面一个元素不一样就行。而在排序问题中，不讲究顺序，通过 used 控制每一个元素只取一遍， 而在当层理论上是可以拿到所有元素的，而实际上只有未被使用过的才是实际上当前层的元素（也就是 used[i] 为 false），所以我们在去重的时候，除了保证与前一个元素要一样之外，还要确保前一个元素并没有被使用。
| 去重步骤 | 组合问题（如组合总和 II） | 排列问题（如全排列 II） |
|---|---|---|
| 前置操作 | 必须先对数组排序（Arrays.sort(nums)），让重复元素相邻 | 必须先对数组排序（Arrays.sort(nums)），让重复元素相邻 |
| 去重条件 | i > startIndex && nums[i] == nums[i-1] | i > 0 && nums[i] == nums[i-1] && !used[i-1] |
| 条件含义 | - i > startIndex：保证是同一层的重复元素（而非同一路径的下一个元素） - 跳过同一层重复元素，避免生成重复组合 | - !used[i-1]：保证是同一层的重复元素（若 used[i-1]=true 则是同一路径的上一个元素） - 跳过同一层重复元素，避免生成重复排列 |
| 核心原理 | 同一层中，相同元素只选第一个，后续的跳过 | 同一层中，相同元素若前一个未被选，则当前元素跳过（避免重复） |
✔ Java 代码模板对比
class Combine {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
dfs(n, k, 1); // 起始索引从 1 开始（对应元素 1~n）
return res;
}
// 核心参数：startIndex（控制下一层遍历起点）
private void dfs(int n, int k, int startIndex) {
// 结束条件：路径长度等于 k
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
// 遍历范围：从 startIndex 开始，避免重复组合
for (int i = startIndex; i <= n; i++) {
path.add(i);
dfs(n, k, i + 1); // 下一层从 i+1 开始
path.remove(path.size() - 1); // 撤销选择（回溯）
}
}
}
class Permute {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used; // 标记元素是否被选中
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
dfs(nums);
return res;
}
// 核心参数：used 数组（标记已选元素），无 startIndex
private void dfs(int[] nums) {
// 结束条件：路径长度等于数组长度
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
// 遍历范围：从 0 开始，遍历所有元素
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // 跳过已选元素
used[i] = true; // 标记选中
path.add(nums[i]); // 选择
dfs(nums); // 下一层继续遍历所有未选元素
path.remove(path.size() - 1); // 撤销选择
used[i] = false; // 恢复标记（回溯）
}
}
}
子集是'所有可能的组合（包括空集）'，核心是'遍历过程中每一步都记录结果'，而非仅在结束条件记录，后端场景中对应'权限子集、配置子集'。
i>startIndex && nums[i]==nums[i-1]）；将字符串/数组'切割'为若干子串/子数组，满足特定条件（如回文、分割后子串符合规则），本质是'组合问题的字符串版'。
substring(start, end) 是左闭右开，需 substring(startIndex, i+1) 才能取到 [startIndex,i] 的子串；在二维棋盘上做'放置决策'（如 N 皇后、数独），核心考察'多维度剪枝'（行、列、对角线），后端场景中对应'布局规划、约束满足'。
....Q.. 格式，注意列的位置；// 通用回溯模板（以组合问题为例）
class BacktrackTemplate {
// 结果集：存储所有合法路径
List<List<Integer>> res = new ArrayList<>();
// 路径：存储当前已选元素
List<Integer> path = new ArrayList<>();
public List<List<Integer>> backtrack(int[] nums, int target) {
// 排序（有重复元素时必加，用于剪枝/去重）
Arrays.sort(nums);
// 启动回溯：起始索引 0，当前和 0
dfs(nums, target, 0, 0);
return res;
}
// 递归函数：核心逻辑
private void dfs(int[] nums, int target, int startIndex, int sum) {
// 1. 结束条件（不同场景不同）
if (sum == target) {
// 必须新建 List，避免引用传递
res.add(new ArrayList<>(path));
return;
}
// 2. 遍历选择列表（从 startIndex 开始，组合/子集；从 0 开始，排列）
for (int i = startIndex; i < nums.length; i++) {
// 3. 剪枝：提前排除无效路径（核心优化）
if (sum + nums[i] > target) {
break; // 数组已排序，后续更大，直接终止循环
}
// 去重：有重复元素时，跳过同一层重复元素
if (i > startIndex && nums[i] == nums[i - 1]) {
continue;
}
// 4. 选择：将当前元素加入路径
path.add(nums[i]);
sum += nums[i];
// 5. 递归：探索下一层（组合：i+1；排列：0；子集：i+1；切割：i+1）
dfs(nums, target, i + 1, sum);
// 6. 撤销选择：回溯，恢复状态
sum -= nums[i];
path.remove(path.size() - 1);
}
}
}
class Combine {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
dfs(n, k, 1);
return res;
}
private void dfs(int n, int k, int startIndex) {
// 结束条件：路径长度==k
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
// 剪枝：剩余可选元素 < 需要的元素数，直接终止（优化）
// 需要的元素数：k - path.size()；剩余可选：n - i + 1
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
path.add(i);
dfs(n, k, i + 1); // 组合：startIndex+1，避免重复
path.remove(path.size() - 1);
}
}
}
class PermuteUnique {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used; // 标记元素是否已选
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums); // 排序去重
used = new boolean[nums.length];
dfs(nums);
return res;
}
private void dfs(int[] nums) {
// 结束条件：路径长度==数组长度
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
// 排列：从 0 开始遍历所有元素
for (int i = 0; i < nums.length; i++) {
// 剪枝 1：已选元素跳过
if (used[i]) continue;
// 剪枝 2：同一层重复元素跳过（核心去重）
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
used[i] = true;
path.add(nums[i]);
dfs(nums); // 排列：无 startIndex，传 0
path.remove(path.size() - 1);
used[i] = false;
}
}
}
class SubsetsWithDup {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums); // 排序去重
dfs(nums, 0);
return res;
}
private void dfs(int[] nums, int startIndex) {
// 子集：每一步都记录结果（核心区别）
res.add(new ArrayList<>(path));
// 结束条件：startIndex 越界，自然终止
for (int i = startIndex; i < nums.length; i++) {
// 去重：同一层重复元素跳过
if (i > startIndex && nums[i] == nums[i - 1]) continue;
path.add(nums[i]);
dfs(nums, i + 1);
path.remove(path.size() - 1);
}
}
}
class Partition {
List<List<String>> res = new ArrayList<>();
List<String> path = new ArrayList<>();
public List<List<String>> partition(String s) {
dfs(s, 0);
return res;
}
private void dfs(String s, int startIndex) {
// 结束条件：切割起点越界
if (startIndex >= s.length()) {
res.add(new ArrayList<>(path));
return;
}
// 遍历切割终点
for (int i = startIndex; i < s.length(); i++) {
// 剪枝：子串不是回文，跳过
if (!isPalindrome(s, startIndex, i)) continue;
// 选择：子串 [startIndex, i]（左闭右闭）
path.add(s.substring(startIndex, i + 1));
dfs(s, i + 1); // 下一次切割起点为 i+1
path.remove(path.size() - 1);
}
}
// 双指针判断回文
private boolean isPalindrome(String s, int l, int r) {
while (l < r) {
if (s.charAt(l) != s.charAt(r)) return false;
l++;
r--;
}
return true;
}
}
class SolveNQueens {
List<List<String>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>(); // 存储每行皇后的列索引
int n;
public List<List<String>> solveNQueens(int n) {
this.n = n;
dfs(0); // 从第 0 行开始
return res;
}
private void dfs(int row) {
// 结束条件：所有行都放了皇后
if (row == n) {
res.add(convertPathToBoard());
return;
}
// 遍历当前行的所有列
for (int col = 0; col < n; col++) {
// 剪枝：判断列、正对角线、反对角线是否有皇后
if (!isValid(row, col)) continue;
path.add(col);
dfs(row + 1); // 处理下一行
path.remove(path.size() - 1);
}
}
// 判断当前位置是否合法
private boolean isValid(int row, int col) {
// 遍历已放皇后的行（path.size() 行）
for (int i = 0; i < path.size(); i++) {
int c = path.get(i);
// 列冲突
if (c == col) return false;
// 正对角线冲突（row - col == i - c）
if (row - col == i - c) return false;
// 反对角线冲突（row + col == i + c）
if (row + col == i + c) return false;
}
return true;
}
// 将 path 转换为棋盘格式（如 ["..Q..", "...Q.", ...]）
private List<String> convertPathToBoard() {
List<String> board = new ArrayList<>();
for (int col : path) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(i == col ? 'Q' : '.');
}
board.add(sb.toString());
}
return board;
}
}
回溯算法二刷的核心逻辑（Java 版）：
本质是'将复杂问题拆解为重叠子问题，通过记录子问题的解（状态）避免重复计算'。
✅✅✅所以动态规划的解题重点就在于找到子问题，存储子问题的答案，再去推到其他子问题的答案
动态规划 = 状态定义 + 状态转移 + 初始条件，核心思想是：
| 要素 | 含义 | Java 实现方式 |
|---|---|---|
| 状态定义 | 定义 dp 数组/变量的含义（最核心、最易出错），回答'dp[i][j] 代表什么？' | int[] dp（一维）、int[][] dp（二维） |
| 状态转移方程 | 子问题之间的递推关系，回答'如何由 dp[i-1][j] 推导出 dp[i][j]？' | 条件判断、数学运算（+/-/max/min） |
| 初始条件 | 最小子问题的解（递归的终止条件），回答'dp[0]/dp[0][0] 的值是多少？' | 数组初始化（dp[0]=0、dp[0][j]=∞等） |
| 遍历顺序 | 按什么顺序计算 dp 数组（需满足'计算 dp[i][j] 时，依赖的状态已计算完成'） | 单层循环（一维）、双层循环（二维，注意 i/j 顺序） |
| 空间优化 | 压缩 dp 数组维度（如二维→一维），减少空间复杂度（后端面试高频追问） | 滚动数组、逆序遍历、变量替代数组 |
遇到以下问题，优先考虑 DP：
| 算法 | 核心思想 | 适用场景 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 动态规划 | 记录子问题解，递推求解 | 有重叠子问题、最优子结构 | O(n²)/O(nm) | O(n)/O(nm)（可优化） |
| 贪心 | 每一步选局部最优 | 贪心选择性质（局部最优→全局最优） | O(n)/O(nlogn) | O(1)/O(n) |
| 回溯 | 暴力枚举所有路径 | 方案数少、需枚举所有可能 | O(2ⁿ)/O(n!) | O(n)（递归栈） |
举例：
Integer.MIN_VALUE（需注意溢出）；Integer.MAX_VALUE；dp[i] %= 1000000007）；DP 90% 的高频题可归为 6 类场景，每类场景都有'状态定义模板 + 转移方程 + 遍历顺序'，二刷需逐个固化。
状态仅与'前一个/前几个'状态相关，dp 数组为一维，是 DP 入门和后端面试最基础的考点（如斐波那契、爬楼梯、打家劫舍）。
dp[i] 代表'前 i 个元素/第 i 个位置达到的目标（最值/方案数）'；dp[i] = f(dp[i-1], dp[i-2], ...)（仅依赖前序有限个状态）；dp[i] 的含义（如 dp[i]=前 i 间房子能偷的最大金额）；dp[i] = max(dp[i-1]（不偷第 i 间）, dp[i-2]+nums[i]（偷第 i 间）)；dp[0]=1（0 级台阶 1 种方式）、dp[1]=1（1 级台阶 1 种方式）；dp[n]。dp[i] 定义为'第 i 级台阶的方式数'，而非'前 i 级'，导致初始条件错误；dp[0]=0、dp[1]=nums[0]，遗漏 dp[0] 会导致 i=2 时越界；背包问题是 DP 的'经典模型'，后端场景中对应'资源分配、成本优化'（如有限预算选最大价值的商品），核心分 4 类，二刷需掌握前 3 类。
状态与'物品数 + 背包容量'相关，dp 数组为二维（可优化为一维），核心是'选/不选第 i 个物品'的决策。
dp[i][j] 代表'前 i 个物品，背包容量为 j 时的最大价值/方案数/可行性'；dp[i][j] = dp[i-1][j]；dp[i][j] = dp[i-1][j-w[i]] + v[i]；dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);做题方法：写递推式可以写二维的方便理解，实际的代码可以用一维或者二维的的，也很方便转换。
LeetCode 416. 分割等和子集（可行性）、LeetCode 494. 目标和（计数）、LeetCode 322. 零钱兑换（最值，特殊 01）。
dp[i][j] = 前 i 个物品，容量 j 时的最大价值；dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（j≥w[i]）；dp[0][j] = 0（无物品时价值为 0）；空间优化：二维→一维，容量逆序遍历（避免重复选同一物品）：
// 一维优化版
int[] dp = new int[bagSize + 1];
for (int i = 0; i < n; i++) {
// 遍历物品
for (int j = bagSize; j >= w[i]; j--) {
// 逆序遍历容量
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
dp[0] = true（容量 0 可达），其余为 false；dp[0] = 1：如目标和，dp[0] = 1（和为 0 的方案数 1）。LeetCode 518. 零钱兑换 II（计数）、LeetCode 322. 零钱兑换（最值）、LeetCode 70. 爬楼梯（特殊完全背包）。
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])（选第 i 个物品后，仍可选第 i 个）；空间优化：一维数组，容量正序遍历（允许重复选）：
int[] dp = new int[bagSize + 1];
for (int i = 0; i < n; i++) {
// 遍历物品
for (int j = w[i]; j <= bagSize; j++) {
// 正序遍历容量
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
dp[0] = 0，其余为 Integer.MAX_VALUE，且计算时需判断 dp[j-w[i]] 是否为无穷大；dp[j] %= MOD。LeetCode 1155. 掷骰子的 N 种方法（分组 + 计数）、自定义分组选品问题。
dp[j] = 容量 j 时的最大价值；dp[j] = max(dp[j], dp[j-w[k]] + v[k])（k 为组内物品）。状态与两个字符串/数组的'前 i 个、前 j 个'元素相关，dp 数组为二维，是后端面试中等题高频考点（如最长公共子序列、编辑距离）。
dp[i][j] 代表'第一个字符串前 i 个、第二个字符串前 j 个的目标值（最长长度/编辑次数）'；dp[i][j] = dp[i-1][j-1] + 1；dp[i][j] = max/min(dp[i-1][j], dp[i][j-1])。【当两个字符串的最后一个字符不同时，这个位置的两个字符不可能同时出现在 xxx 中，所以各取一个进行尝试】dp[i][j] 数组常见的两种定义方式：以 i 结尾和以 j 结尾的字符串字符串的前 i 个和前 j 个字符串的 [i,j] 区间（属于区间 dp 后面的章节会提到）
dp[i][j] = 字符串 s1 前 i 个、s2 前 j 个的最长公共子序列长度；s1[i-1] == s2[j-1]（字符匹配）：dp[i][j] = dp[i-1][j-1] + 1；dp[i][j] = max(dp[i-1][j], dp[i][j-1])；dp[0][j] = 0、dp[i][0] = 0（空字符串的 LCS 长度为 0）；为了方便初始化，一般会采用 int[][] dp = new int[word1.length() + 1][word2.length() + 1]。其实我们可以理解为添加了字符串的长度为 0 的情况，也就是多了一个占位，所以 dp[i][j] 实际上表示的是字符串 a 的前 i - 1 个字符串 b 的前 j - 1 个（或者以此结尾）
例如经典的编辑距离问题：
class Solution {
public int minDistance(String word1, String word2) {
// dp[i][j] 表示从 word1[0,i - 1] 转化到 word2[0,j - 1] 所需要的最少操作数
// if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
// if(word1[i - 1] != word2[j - 1]) min(dp[i - 1][j - 1],dp[i - 1][j],dp[i][j - 1]) + 1
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 1; i <= word1.length(); i++) dp[i][0] = i;
for (int j = 1; j <= word2.length(); j++) dp[0][j] = j;
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
}
return dp[word1.length()][word2.length()];
}
}
dp[i][i] = 1（单个字符是回文），而非 0；状态与'区间 [i,j]'相关，dp 数组为二维，核心是'从小区间扩展到大全区间'，后端场景中对应'区间合并、字符串分割'。
dp[i][j] = 区间 [i,j] 内的最优解（最值/方案数）；dp[i][j] = f(dp[i][k], dp[k+1][j])（k 为区间分割点，i≤k<j）；dp[i][j] 表示字符串 [i,j] 是否是最长回文子串；dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1];class Solution {
public String longestPalindrome(String s) {
// dp[i][j] 表示字符串 [i,j] 是否是最长回文子串
// dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1];
boolean[][] dp = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) dp[i][i] = true;
int max = 1;
int offest = 0;
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i + 1; j < s.length(); j++) {
if (s.charAt(i) != s.charAt(j)) dp[i][j] = false;
else {
if (j - i == 1) dp[i][j] = true;
else dp[i][j] = dp[i + 1][j - 1];
if (dp[i][j] && j - i + 1 > max) {
offest = i;
max = j - i + 1;
}
}
}
}
return s.substring(offest, offest + max);
}
}
dp[i][j] = 合并区间 [i,j] 的石子的最小代价；dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j])（sum[i][j] 为区间 [i,j] 石子和）；dp[i][i] = 0（单个石子无需合并）；遍历顺序：
for (int len = 2; len <= n; len++) {
// 区间长度
for (int i = 1; i + len - 1 <= n; i++) {
// 区间起点
int j = i + len - 1; // 区间终点
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
// 分割点
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]);
}
}
}
dp[i][j] 初始化为 0，导致最小值计算错误。状态定义在树上，通过后序遍历（自底向上）计算子树的状态，后端场景中对应'树形结构的最值/方案数'（如公司人员分配、树的直径）。
dp[node][0/1] 代表'以 node 为根的子树，node 选/不选时的最优解'；dp[node][0]：不偷 node 时，子树的最大金额；dp[node][1]：偷 node 时，子树的最大金额；dp[node][0] = max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1])；dp[node][1] = node.val + dp[left][0] + dp[right][0]；dp[null][0] = dp[null][1] = 0；将多维状态（如二维）压缩为一维，或用二进制数表示状态（如集合），后端场景中对应'有限状态的优化'（如旅行商问题、状态压缩背包）。
mask=5（101）代表第 0、2 个元素被选中）；dp[mask] = f(dp[mask ^ (1<<i)])（mask 为当前状态，i 为选中的元素）；dp[mask][i] = 访问过 mask 表示的城市，最后在城市 i 的最小路径；dp[mask][i] = min(dp[mask ^ (1<<i)][j] + dist[j][i])（j 为前一个城市）；dp[1<<i][i] = 0（仅访问城市 i，路径为 0）；1<<i 易误写为 1<<(i-1)，导致状态表示错误；dp[mask][i] 初始化为无穷大，未设置起点状态。// 通用 DP 模板（以二维 DP 为例）
class DPGeneralTemplate {
public int dpTemplate(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
// 1. 状态定义：dp[i][j] 代表 nums1 前 i 个、nums2 前 j 个的目标值
int[][] dp = new int[n + 1][m + 1];
// 2. 初始条件
for (int i = 0; i <= n; i++) {
dp[i][0] = 0; // 示例初始值，根据场景调整
}
for (int j = 0; j <= m; j++) {
dp[0][j] = 0;
}
// 3. 遍历顺序：先 i 后 j（根据依赖调整）
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 4. 状态转移方程（核心，根据场景调整）
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 5. 返回最终状态
return dp[n][m];
}
}
class ZeroOneKnapsack {
// 题目：判断数组是否能分割为两个子集，和相等（01 背包可行性）
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) sum += num;
if (sum % 2 != 0) return false; // 和为奇数，无法分割
int target = sum / 2;
// 空间优化：一维 dp，dp[j] = 容量 j 是否可达
boolean[] dp = new boolean[target + 1];
dp[0] = true; // 初始条件：容量 0 可达
// 遍历物品（01 背包：先物品后容量，容量逆序）
for (int num : nums) {
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num]; // 状态转移：不选/选当前物品
}
}
return dp[target];
}
}
class CompleteKnapsack {
// 题目：给定金额和无限数量的硬币，求组成金额的组合数
public int change(int amount, int[] coins) {
// 状态定义：dp[j] = 金额 j 的组合数
int[] dp = new int[amount + 1];
dp[0] = 1; // 初始条件：金额 0 的组合数为 1
// 遍历物品（完全背包：先物品后容量，容量正序）
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
dp[j] += dp[j - coin]; // 状态转移：选当前硬币
// dp[j] %= 1000000007; // 大数取模（题目要求时加）
}
}
return dp[amount];
}
}
class LIS {
// O(n²) DP 解法 + O(nlogn) 贪心 + 二分优化
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// 1. O(n²) DP 解法
int[] dp = new int[n];
Arrays.fill(dp, 1); // 初始条件：每个元素自身是长度为 1 的子序列
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
// 2. O(nlogn) 贪心 + 二分优化（二刷必掌握）
// List<Integer> tails = new ArrayList<>();
// for (int num : nums) {
// int idx = Collections.binarySearch(tails, num);
// if (idx < 0) idx = -idx - 1;
// if (idx == tails.size()) tails.add(num);
// else tails.set(idx, num);
// }
// return tails.size();
return maxLen;
}
}
class LCS {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
// 状态定义：dp[i][j] = text1 前 i 个、text2 前 j 个的 LCS 长度
int[][] dp = new int[n + 1][m + 1];
// 遍历顺序：先 i 后 j
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 状态转移
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
}
class TreeDP {
// 题目：二叉树中偷节点，不能偷相邻节点，求最大金额
public int rob(TreeNode root) {
int[] res = dfs(root);
return Math.max(res[0], res[1]); // 0：不偷根，1：偷根
}
// 后序遍历，返回 int[2]：[不偷当前节点的最大值，偷当前节点的最大值]
private int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0}; // 空节点初始条件
int[] left = dfs(node.left); // 左子树状态
int[] right = dfs(node.right); // 右子树状态
// 状态转移：
// 不偷当前节点：左右子树可偷可不偷，取最大值
int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
// 偷当前节点：左右子树都不能偷
int rob = node.val + left[0] + right[0];
return new int[]{notRob, rob};
}
// 二叉树节点定义
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
}
动态规划二刷的核心逻辑（Java 版）：
✅ 高频避坑点（二刷必记）
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online