【算法训练营 · 二刷总结篇】回溯算法、动态规划部分

Ne0inhk

— 50 min read

文章目录

回溯算法部分

回溯算法是后端面试中等题核心考察点（占比60%+），本质是“深度优先搜索（DFS）+ 状态回退”的暴力搜索优化，核心解决“多阶段决策”类问题（组合、排列、子集、切割、棋盘）。

核心知识点

✅ 核心定义与本质

回溯算法 = 递归（深度优先遍历） + 状态回退（撤销选择），本质是“暴力枚举所有可能的决策路径”：

  • 对每一个决策阶段，先“选择”一个选项 → 递归探索后续路径 → 递归返回后“撤销选择” → 尝试下一个选项；
  • 与纯暴力枚举的区别：通过“撤销选择”复用同一容器存储路径，节省空间，且能通过剪枝提前排除无效路径（优化时间）。

✅ 核心三要素（回溯的“灵魂”）

要素含义Java实现方式
路径已做出的选择（如组合问题中已选的数字、N皇后中已放皇后的位置）List<Integer> path、StringBuilder
选择列表当前阶段可选择的选项（如组合问题中未选的数字、棋盘问题中可放皇后的列）数组/集合、boolean[] used（去重）
结束条件到达决策树底部，需记录结果（如组合长度达标、棋盘遍历完成）路径长度==目标长度、索引越界等

✅ 时间&空间复杂度（二刷必懂，应对面试官追问）

  • 时间复杂度：本质是暴力枚举，通常为指数级/阶乘级：
    • 组合/子集问题： O ( 2 n ) O(2^n) O(2n)（每个元素选或不选）；
    • 排列问题： O ( n ! ) O(n!) O(n!)（n个元素的全排列）；
    • 剪枝能减少实际执行时间，但理论复杂度不变。
  • 空间复杂度： O ( n ) O(n) O(n)（递归栈深度 + 路径存储容器，n为决策阶段数）。

✅ Java实现核心要点（避坑基础）

  1. 容器回溯的核心：Java中List/StringBuilder是引用传递，递归中添加元素后，必须在递归返回后“撤销选择”（如path.remove(path.size()-1)），否则会污染其他路径；
  2. 去重方式：
    • 排列问题：boolean[] used（标记元素是否已选，避免重复选同一元素）；
    • 有重复元素的组合/排列：先排序 + used数组（跳过同一层重复元素）；
  3. 剪枝时机：在“选择”前判断（如组合总和超过目标值时直接return），而非“选择后”，最大化减少无效递归；
  4. 结果集存储：需新建容器存储路径（如res.add(new ArrayList<>(path))），而非直接add(path)（引用传递会导致结果集被后续修改）。

✅ 回溯与递归/DFS的关系

  • 递归是回溯的实现载体：回溯必须通过递归实现深度优先遍历；
  • DFS是回溯的遍历方式：回溯的核心是“选-试-撤”，DFS是遍历决策树的手段；
  • 区别：纯DFS仅遍历所有节点，回溯多了“选择-撤销”的状态管理。

技巧方法

回溯90%的高频题可归为5类场景，每类场景都有“通用模板+专属剪枝/去重技巧”，二刷需逐个固化。

✅ 技巧一：组合问题（★★★★★ 占比30%+，核心中的核心）

核心定位

考察“无顺序的元素选择”（如选[1,2]和[2,1]视为同一组合），后端面试中等题高频（如组合总和、电话号码的字母组合）。

核心原理
  • 组合的核心：不重复选（同一元素仅选一次） + 不考虑顺序；
  • 控制顺序的关键：通过“起始索引”（startIndex）限制选择列表，避免重复组合（如选1后，后续仅从2开始选，而非从0重新选）。
适用场景
  • 无重复元素组合（LeetCode 77）、有重复元素组合（LeetCode 40）；
  • 组合总和（LeetCode 39、40、216）、电话号码的字母组合（LeetCode 17）。
核心思路（四步法，必背）
  1. 参数定义：递归函数需包含「路径path、结果集res、起始索引startIndex、目标值/其他约束」；
  2. 结束条件：路径长度达标（如组合长度k）或路径和达标（如组合总和=target），将path拷贝加入res；
  3. 遍历选择列表：从startIndex开始遍历（避免重复组合）：
    • 剪枝：提前排除无效选择（如组合总和超过target，直接break）；
    • 选择：将当前元素加入path；
    • 递归：传入startIndex+1（同一元素仅选一次），探索后续路径；
    • 撤销选择：从path中移除当前元素（回溯）；
  4. 去重（有重复元素时）：先排序数组 + 遍历中跳过同一层重复元素（i>startIndex && nums[i]==nums[i-1] && !used[i-1]）。
高频经典题
  1. LeetCode 77. 组合（基础模板题，无重复元素，二刷速过）；
  2. LeetCode 39. 组合总和（无重复元素，元素可重复选，核心改startIndex为i）；
  3. LeetCode 40. 组合总和II（有重复元素，需排序+used去重）；
  4. LeetCode 17. 电话号码的字母组合（多维度选择，无startIndex，用索引遍历数字）。
避坑点
  1. 用startIndex控制顺序，而非used数组：组合无需used（排列才需要），startIndex是避免重复组合的核心（如选1后仅从2开始选）；
  2. 元素可重复选时，递归startIndex传i而非i+1：如组合总和中，数字可重复选，需从当前i继续，而非i+1；
  3. 有重复元素时未排序：排序是去重的前提（同一层重复元素相邻，便于跳过）；
  4. 结果集直接add(path)：Java中path是引用，需res.add(new ArrayList<>(path))，否则结果集所有元素指向同一path；
  5. 剪枝时机错误：如组合总和中，需在遍历前判断sum + nums[i] > target则break（而非continue），因为数组已排序，后续元素更大。

✅ 技巧二：排列问题（★★★★ 占比20%+，去重是核心）

核心定位

考察“有顺序的元素选择”（如[1,2]和[2,1]视为不同排列），后端面试中常与“去重”结合考察（有重复元素的排列）。

核心原理
  • 排列的核心：元素可全选 + 考虑顺序；
  • 去重的关键：
    • 已选元素不能重复使用：boolean[] used数组标记元素是否已选，避免同一路径重复选；
    • 相同结果的去重：有重复元素时，需排序 + 跳过同一层重复且未选的元素。
适用场景
  • 无重复元素排列（LeetCode 46）、有重复元素排列（LeetCode 47）；
  • 字符串的全排列（含重复字符）。
核心思路（四步法）
  1. 参数定义：递归函数包含「路径path、结果集res、原数组nums、used数组」；
  2. 结束条件：path长度==nums.length，将path拷贝加入res；
  3. 遍历选择列表：从0开始遍历（排列需考虑所有未选元素）：
    • 剪枝/去重：
      • 已选元素跳过（used[i]==true）；
      • 有重复元素时，跳过同一层重复元素（i>0 && nums[i]==nums[i-1] && !used[i-1]）；
      • 注意：之所以有!used[i-1]是因为如果used[i - 1]为true的话，那么说明这个元素已经被其他层级使用过了，并不是当前层级的。并且使用nums[i]==nums[i-1]进行去重，需要对数组进行排序才能行之有效！
    • 选择：标记used[i]=true，将nums[i]加入path；
    • 递归：探索后续路径；
    • 撤销选择：标记used[i]=false，从path移除nums[i]；
  4. 收尾：无额外处理，递归结束后res即为所有排列。
高频经典题
  1. LeetCode 46. 全排列（无重复元素，基础模板题）；
  2. LeetCode 47. 全排列II（有重复元素，排序+used去重核心）。
避坑点
  1. 排列用startIndex而非used：排列需从0遍历所有元素，startIndex是组合的专属，排列必须用used标记已选元素；
  2. 有重复元素时，去重条件错误：需!used[i-1]（同一层重复）而非used[i-1]（同一路径重复），前者跳过同一层重复，后者跳过同一路径重复（会漏解）；
  3. 未排序直接去重：重复元素不相邻时，无法通过nums[i]==nums[i-1]判断，必须先排序；
  4. 递归参数传递used数组时拷贝：Java中数组是引用传递，无需拷贝（回溯时修改used[i]即可），拷贝会增加时间复杂度。

✅易错点：组合与排序的解题区别

  • 组合：startIndex 控顺序，选过的元素后面不再选，结果是集合；
  • 排列：used 数组控已选，选过的元素同一路径不再选，结果是序列。
其实可以再抽象一层，因为很多题目不会直接告诉你是组合还是排序：顺序层面：考虑顺序used，不考虑顺序用offest有重复元素的去重：排序是前提，考虑顺序那么去重的时候除了与前面一个元素相同，还要是当前层的元素

✔ 核心定义与目标差异

维度组合问题排列问题
核心本质从 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代码模板对比

  1. 组合问题模板（无重复元素，如LeetCode 77. 组合）
classCombine{List<List<Integer>> res =newArrayList<>();List<Integer> path =newArrayList<>();publicList<List<Integer>>combine(int n,int k){dfs(n, k,1);// 起始索引从1开始（对应元素1~n）return res;}// 核心参数：startIndex（控制下一层遍历起点）privatevoiddfs(int n,int k,int startIndex){// 结束条件：路径长度等于kif(path.size()== k){ res.add(newArrayList<>(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);// 撤销选择（回溯）}}}
  1. 排列问题模板（无重复元素，如LeetCode 46. 全排列）
classPermute{List<List<Integer>> res =newArrayList<>();List<Integer> path =newArrayList<>();boolean[] used;// 标记元素是否被选中publicList<List<Integer>>permute(int[] nums){ used =newboolean[nums.length];dfs(nums);return res;}// 核心参数：used数组（标记已选元素），无startIndexprivatevoiddfs(int[] nums){// 结束条件：路径长度等于数组长度if(path.size()== nums.length){ res.add(newArrayList<>(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;// 恢复标记（回溯）}}}

✅ 技巧三：子集问题（★★★★ 占比15%+，组合的变种）

核心定位

子集是“所有可能的组合（包括空集）”，核心是“遍历过程中每一步都记录结果”，而非仅在结束条件记录，后端场景中对应“权限子集、配置子集”。

核心原理
  • 子集的核心：每个元素有“选”或“不选”两种选择，遍历决策树的所有节点（而非仅叶子节点）；
  • 与组合的区别：组合仅记录叶子节点（路径长度达标），子集记录所有节点（每一步的路径都是一个子集）。
适用场景
  • 无重复元素子集（LeetCode 78）、有重复元素子集（LeetCode 90）；
  • 子集求和（如子集的和为目标值）。
核心思路（四步法）
  1. 参数定义：递归函数包含「路径path、结果集res、起始索引startIndex、原数组nums」；
  2. 结果记录：进入递归后，先将当前path拷贝加入res（每一步都是一个子集）；
  3. 遍历选择列表：从startIndex开始遍历（避免重复子集）：
    • 去重（有重复元素时）：跳过同一层重复元素（i>startIndex && nums[i]==nums[i-1]）；
    • 选择：将nums[i]加入path；
    • 递归：传入startIndex+1，探索后续路径；
    • 撤销选择：从path移除nums[i]；
  4. 结束条件：startIndex >= nums.length（递归自然终止，无需额外判断）。
高频经典题
  1. LeetCode 78. 子集（无重复元素，基础模板题）；
  2. LeetCode 90. 子集II（有重复元素，排序+跳过同一层重复）。
避坑点
  1. 结果记录时机错误：子集需在递归开头记录（每一步都是子集），而非结束条件（否则仅记录全量元素）；
  2. 用used数组去重：子集无需used，仅需startIndex+排序去重（组合的去重逻辑）；
  3. 空集未记录：递归开头记录path，空集会被自然记录（初始path为空，第一次递归就add）；
  4. 有重复元素时未排序：导致同一层重复元素无法被跳过，子集重复。

✅ 技巧四：切割问题（★★★ 占比10%+，组合的变形）

核心定位

将字符串/数组“切割”为若干子串/子数组，满足特定条件（如回文、分割后子串符合规则），本质是“组合问题的字符串版”。

核心原理
  • ※切割的核心：用startIndex标记切割起点，每次选择“切割终点”（i），子串为[startIndex, i]；
  • 与组合的对应：切割终点i = 组合中的“选择项”，子串[startIndex,i] = 组合中的“选中元素”。
适用场景
  • 分割回文串（LeetCode 131）、复原IP地址（LeetCode 93）。
核心思路（四步法）
  1. 参数定义：递归函数包含「原字符串s、路径path（存储子串）、结果集res、起始索引startIndex」；
  2. 结束条件：startIndex >= s.length()，将path拷贝加入res；
  3. 遍历选择列表：从startIndex开始遍历（切割起点），i为切割终点：
    • 剪枝：判断子串[s[startIndex…i]]是否符合条件（如回文、IP段合法），不符合则跳过；
    • 选择：将子串加入path；
    • 递归：传入i+1（下一次切割起点为i+1）；
    • 撤销选择：从path移除子串；
  4. 收尾：无额外处理。
高频经典题
  1. LeetCode 131. 分割回文串（核心模板题，回文判断+切割）；
  2. LeetCode 93. 复原IP地址（IP段合法性判断+切割次数限制）。
避坑点
  1. 子串索引错误：Java中substring(start, end)是左闭右开，需substring(startIndex, i+1)才能取到[startIndex,i]的子串；
  2. 回文判断效率低：可提前用动态规划预处理回文子串（二刷进阶优化，基础版用双指针即可）；
  3. IP地址切割未限制次数：IP地址最多切割3次（4个段），需在递归中加层数限制（如path.size()<4），否则会生成无效IP；
  4. IP段合法性判断不全：需满足① 0<=数值<=255 ② 不能以0开头（除非段是"0"）。

✅ 技巧五：棋盘问题（★★★ 占比15%+，剪枝是关键）

核心定位

在二维棋盘上做“放置决策”（如N皇后、数独），核心考察“多维度剪枝”（行、列、对角线），后端场景中对应“布局规划、约束满足”。

核心原理
  • 棋盘问题的核心：按行/列遍历，每一步选择“合法位置”放置元素，通过剪枝排除攻击位置；
  • N皇后：每行放一个皇后，需判断列、正对角线（行-列=常数）、反对角线（行+列=常数）是否已有皇后；
  • 数独：每个空格填1-9，需判断行、列、3x3小宫格是否已有该数字。
适用场景
  • N皇后问题（LeetCode 51、52）、解数独（LeetCode 37）。
核心思路（以N皇后为例，四步法）
  1. 参数定义：递归函数包含「棋盘大小n、路径path（存储每行皇后的列索引）、结果集res、当前行row」；
  2. 结束条件：row == n，将path转换为棋盘格式加入res；
  3. 遍历选择列表：遍历当前行的每一列col：
    • 剪枝：判断(col, 正对角线, 反对角线)是否已有皇后，有则跳过；
    • 选择：将col加入path，标记该列/对角线为已用；
    • 递归：处理下一行（row+1）；
    • 撤销选择：从path移除col，取消列/对角线标记；
  4. 收尾：无额外处理。
高频经典题
  1. LeetCode 51. N皇后（核心模板题，多维度剪枝）；
  2. LeetCode 37. 解数独（进阶，填充+验证，需回溯+递归返回值）。
避坑点
  1. 对角线判断错误：正对角线（row - col）可能为负，需加偏移量（如n）转为正数；反对角线（row + col）无需偏移；
  2. 棋盘转换错误：N皇后中path存储的是“每行皇后的列索引”，需转换为....Q..格式，注意列的位置；
  3. 数独未提前遍历所有空格：解数独需先收集所有空格坐标，再逐个填充，避免重复遍历；
  4. 剪枝不彻底：N皇后中，每行仅需判断已放皇后的行（无需判断所有行），减少判断次数。

通用代码模板

✔ 模板1：回溯通用模板（所有场景的基础）

// 通用回溯模板（以组合问题为例）classBacktrackTemplate{// 结果集：存储所有合法路径List<List<Integer>> res =newArrayList<>();// 路径：存储当前已选元素List<Integer> path =newArrayList<>();publicList<List<Integer>>backtrack(int[] nums,int target){// 排序（有重复元素时必加，用于剪枝/去重）Arrays.sort(nums);// 启动回溯：起始索引0，当前和0dfs(nums, target,0,0);return res;}// 递归函数：核心逻辑privatevoiddfs(int[] nums,int target,int startIndex,int sum){// 1. 结束条件（不同场景不同）if(sum == target){// 必须新建List，避免引用传递 res.add(newArrayList<>(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);}}}

✔ 模板2：组合问题（LeetCode 77. 组合）

classCombine{List<List<Integer>> res =newArrayList<>();List<Integer> path =newArrayList<>();publicList<List<Integer>>combine(int n,int k){dfs(n, k,1);return res;}privatevoiddfs(int n,int k,int startIndex){// 结束条件：路径长度==kif(path.size()== k){ res.add(newArrayList<>(path));return;}// 剪枝：剩余可选元素 < 需要的元素数，直接终止（优化）// 需要的元素数：k - path.size()；剩余可选：n - i + 1for(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);}}}

✔ 模板3：排列问题（LeetCode 47. 全排列II，有重复元素）

classPermuteUnique{List<List<Integer>> res =newArrayList<>();List<Integer> path =newArrayList<>();boolean[] used;// 标记元素是否已选publicList<List<Integer>>permuteUnique(int[] nums){Arrays.sort(nums);// 排序去重 used =newboolean[nums.length];dfs(nums);return res;}privatevoiddfs(int[] nums){// 结束条件：路径长度==数组长度if(path.size()== nums.length){ res.add(newArrayList<>(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;}}}

✔ 模板4：子集问题（LeetCode 90. 子集II，有重复元素）

classSubsetsWithDup{List<List<Integer>> res =newArrayList<>();List<Integer> path =newArrayList<>();publicList<List<Integer>>subsetsWithDup(int[] nums){Arrays.sort(nums);// 排序去重dfs(nums,0);return res;}privatevoiddfs(int[] nums,int startIndex){// 子集：每一步都记录结果（核心区别） res.add(newArrayList<>(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);}}}

✔ 模板5：切割问题（LeetCode 131. 分割回文串）

classPartition{List<List<String>> res =newArrayList<>();List<String> path =newArrayList<>();publicList<List<String>>partition(String s){dfs(s,0);return res;}privatevoiddfs(String s,int startIndex){// 结束条件：切割起点越界if(startIndex >= s.length()){ res.add(newArrayList<>(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);}}// 双指针判断回文privatebooleanisPalindrome(String s,int l,int r){while(l < r){if(s.charAt(l)!= s.charAt(r))returnfalse; l++; r--;}returntrue;}}

✔ 模板6：棋盘问题（LeetCode 51. N皇后）

classSolveNQueens{List<List<String>> res =newArrayList<>();List<Integer> path =newArrayList<>();// 存储每行皇后的列索引int n;publicList<List<String>>solveNQueens(int n){this.n = n;dfs(0);// 从第0行开始return res;}privatevoiddfs(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);}}// 判断当前位置是否合法privatebooleanisValid(int row,int col){// 遍历已放皇后的行（path.size()行）for(int i =0; i < path.size(); i++){int c = path.get(i);// 列冲突if(c == col)returnfalse;// 正对角线冲突（row - col == i - c）if(row - col == i - c)returnfalse;// 反对角线冲突（row + col == i + c）if(row + col == i + c)returnfalse;}returntrue;}// 将path转换为棋盘格式（如["..Q..", "...Q.", ...]）privateList<String>convertPathToBoard(){List<String> board =newArrayList<>();for(int col : path){StringBuilder sb =newStringBuilder();for(int i =0; i < n; i++){ sb.append(i == col ?'Q':'.');} board.add(sb.toString());}return board;}}

总结

回溯算法二刷的核心逻辑（Java版）：

  1. 通用模板是根基：记住“选-试-撤”三步，所有场景都是模板的变形；
  2. 场景差异是关键：
    • 组合：startIndex控顺序，无used；
    • 排列：used控已选，无startIndex；
    • 子集：每步记录结果，startIndex控重复；
    • 切割：子串判断+startIndex；
    • 棋盘：多维度剪枝+行列遍历；
  3. 剪枝是优化核心：提前排除无效路径，减少递归次数；
  4. Java特性要注意：引用传递、容器回溯、字符串索引，规避空指针和结果错误。

动态规划部分

本质是“将复杂问题拆解为重叠子问题，通过记录子问题的解（状态）避免重复计算”。

✅✅✅所以动态规划的解题重点就在于找到子问题，存储子问题的答案，再去推到其他子问题的答案

核心知识点

✅ 核心定义与本质

动态规划 = 状态定义 + 状态转移 + 初始条件，核心思想是：

  • 「重叠子问题」：大问题可拆分为多个子问题，且子问题会被重复计算（如斐波那契数列中f(5)需计算f(4)和f(3)，f(4)又需计算f(3)）；
  • 「最优子结构」：大问题的最优解由子问题的最优解组成（如最短路径中，到终点的最短路径 = 到前驱节点的最短路径 + 前驱到终点的距离）；
  • 「无后效性」：某阶段的状态仅由前序状态决定，与后续决策无关（如背包问题中，dp[i][j]仅由dp[i-1][j]或dp[i-1][j-w[i]]决定）。

✅ 动态规划核心五要素（DP的“灵魂”，缺一不可）

要素含义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）

遇到以下问题，优先考虑DP：

  1. 求“最值”（最长/最短/最大/最小）、“方案数”（有多少种方式）、“可行性”（是否能达到目标）；
  2. 问题可拆分为重叠子问题，且满足最优子结构、无后效性；
  3. 暴力解法（回溯/递归）超时（时间复杂度O(2ⁿ)/O(n!)），需通过记录子问题解优化。

✅ DP vs 贪心 vs 回溯（二刷必懂区别，应对面试官追问）

算法核心思想适用场景时间复杂度空间复杂度
动态规划记录子问题解，递推求解有重叠子问题、最优子结构O(n²)/O(nm)O(n)/O(nm)（可优化）
贪心每一步选局部最优贪心选择性质（局部最优→全局最优）O(n)/O(nlogn)O(1)/O(n)
回溯暴力枚举所有路径方案数少、需枚举所有可能O(2ⁿ)/O(n!)O(n)（递归栈）

举例：

  • 找零钱（无面值限制）：贪心（选最大面值）仅在特定面值（如人民币）有效，DP能解决所有情况；
  • 最长递增子序列：DP（O(n²)）/贪心+二分（O(nlogn)），回溯会超时。

✅ 时间&空间复杂度（二刷必懂，应对追问）

  • 时间复杂度：等于dp数组的大小 × 每个状态的计算时间（通常O(1)）：
    • 一维DP（如LIS）：O(n²)；
    • 二维DP（如LCS）：O(nm)；
    • 背包问题（二维）：O(nm)，优化后一维：O(m)。
  • 空间复杂度：
    • 未优化：O(n)/O(nm)；
    • 优化后：O(1)/O(m)（如背包问题滚动数组）。

✅ Java实现DP的核心要点（避坑基础）

  1. 数组初始化：
    • 求“最大值”：初始化为Integer.MIN_VALUE（需注意溢出）；
    • 求“最小值”：初始化为Integer.MAX_VALUE；
    • 求“方案数”：初始化为0（边界条件设为1，如dp[0]=1）；
  2. 边界处理：避免数组越界（如dp[i-1]需保证i≥1）；
  3. 空间优化：
    • 二维→一维：需注意遍历顺序（01背包逆序，完全背包正序）；
    • 一维→变量：仅依赖前1-2个状态时（如斐波那契数列）；
  4. 大数处理：方案数可能溢出，需按题目要求取模（如dp[i] %= 1000000007）；
  5. 浮点数精度：避免用float/double存储状态，优先用int/long（如路径概率可转分数）。

技巧方法

DP 90%的高频题可归为6类场景，每类场景都有“状态定义模板+转移方程+遍历顺序”，二刷需逐个固化。

✅ 技巧一：线性DP（★★★★★ 占比30%+，基础中的基础）

核心定位

状态仅与“前一个/前几个”状态相关，dp数组为一维，是DP入门和后端面试最基础的考点（如斐波那契、爬楼梯、打家劫舍）。

核心原理
  • 状态定义：dp[i]代表“前i个元素/第i个位置达到的目标（最值/方案数）”；
  • 转移方程：dp[i] = f(dp[i-1], dp[i-2], ...)（仅依赖前序有限个状态）；
  • 遍历顺序：从左到右（依赖前序状态）。
适用场景
  • 递推类：斐波那契数列、爬楼梯；
  • 最值类：打家劫舍、最大子数组和、买卖股票的最佳时机；
  • 计数类：不同路径、整数拆分。
核心思路（四步法）
  1. 状态定义：明确dp[i]的含义（如dp[i]=前i间房子能偷的最大金额）；
  2. 转移方程：分析第i个位置的选择（选/不选），推导递推关系：
    • 例（打家劫舍）：dp[i] = max(dp[i-1]（不偷第i间）, dp[i-2]+nums[i]（偷第i间）)；
  3. 初始条件：
    • 例（爬楼梯）：dp[0]=1（0级台阶1种方式）、dp[1]=1（1级台阶1种方式）；
  4. 遍历顺序：从2到n（依赖dp[0]、dp[1]），最后返回dp[n]。
高频经典题
  1. LeetCode 70. 爬楼梯（计数类线性DP，基础模板）；
  2. LeetCode 198. 打家劫舍（最值类线性DP，选/不选思路）；
  3. LeetCode 53. 最大子数组和（Kadane算法，线性DP优化）；
  4. LeetCode 121. 买卖股票的最佳时机（单次交易，线性DP）。
避坑点
  1. 状态定义模糊：如爬楼梯中dp[i]定义为“第i级台阶的方式数”，而非“前i级”，导致初始条件错误；
  2. 初始条件遗漏：如打家劫舍中dp[0]=0、dp[1]=nums[0]，遗漏dp[0]会导致i=2时越界；
  3. 空间优化未做：如斐波那契数列用一维数组而非两个变量（优化后空间O(1)）；
  4. 遍历顺序错误：线性DP必须从左到右，反向遍历会导致依赖的状态未计算。

✅ 技巧二：背包问题（★★★★★ 占比25%+，后端高频）

背包问题是DP的“经典模型”，后端场景中对应“资源分配、成本优化”（如有限预算选最大价值的商品），核心分4类，二刷需掌握前3类。

核心定位

状态与“物品数+背包容量”相关，dp数组为二维（可优化为一维），核心是“选/不选第i个物品”的决策。

核心原理（通用）
  • 状态定义：dp[i][j]代表“前i个物品，背包容量为j时的最大价值/方案数/可行性”；
  • 转移方程：
    • 不选第i个物品：dp[i][j] = dp[i-1][j]；
    • 选第i个物品（需j≥w[i]）：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]);
  • 遍历顺序：先物品后容量（二维），优化后一维需注意顺序（01逆序，完全正序）。
做题方法：写递推式可以写二维的方便理解，实际的代码可以用一维或者二维的的，也很方便转换。
子场景1：01背包（每个物品仅选1次，核心）
适用场景

LeetCode 416. 分割等和子集（可行性）、LeetCode 494. 目标和（计数）、LeetCode 322. 零钱兑换（最值，特殊01）。

核心思路
  1. 状态定义：dp[i][j] = 前i个物品，容量j时的最大价值；
  2. 转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（j≥w[i]）；
  3. 初始条件：dp[0][j] = 0（无物品时价值为0）；

空间优化：二维→一维，容量逆序遍历（避免重复选同一物品）：

// 一维优化版int[] dp =newint[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）。
子场景2：完全背包（每个物品可选无限次）
适用场景

LeetCode 518. 零钱兑换II（计数）、LeetCode 322. 零钱兑换（最值）、LeetCode 70. 爬楼梯（特殊完全背包）。

核心思路
  1. 状态定义：同01背包；
  2. 转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])（选第i个物品后，仍可选第i个）；

空间优化：一维数组，容量正序遍历（允许重复选）：

int[] dp =newint[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]);}}
避坑点
  • 混淆01和完全背包的遍历顺序：01逆序、完全正序，记反会导致结果错误；
  • 零钱兑换（最值）初始条件错误：dp[0] = 0，其余为Integer.MAX_VALUE，且计算时需判断dp[j-w[i]]是否为无穷大；
  • 计数问题未取模：如零钱兑换II，方案数可能溢出，需dp[j] %= MOD。
子场景3：分组背包（物品分组成组，每组仅选1个）
适用场景

LeetCode 1155. 掷骰子的N种方法（分组+计数）、自定义分组选品问题。

核心思路
  1. 状态定义：dp[j] = 容量j时的最大价值；
  2. 遍历顺序：先容量（逆序）→ 再分组 → 再组内物品（保证每组仅选1个）；
  3. 转移方程：dp[j] = max(dp[j], dp[j-w[k]] + v[k])（k为组内物品）。

✅ 技巧三：子序列/子串DP（★★★★ 占比15%+，中等题核心）

核心定位

状态与两个字符串/数组的“前i个、前j个”元素相关，dp数组为二维，是后端面试中等题高频考点（如最长公共子序列、编辑距离）。

核心原理
  • 子序列：不要求连续（如“abc”的子序列“ac”）；
  • 子串：要求连续（如“abc”的子串“ab”）；
  • 状态定义：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后面的章节会提到）
适用场景
  • 子序列：最长公共子序列（LCS）、最长递增子序列（LIS）、最长回文子序列；
  • 子串：最长公共子串、最长回文子串；
  • 编辑类：编辑距离、两个字符串的删除操作。
核心思路（以LCS为例）
  1. 状态定义：dp[i][j] = 字符串s1前i个、s2前j个的最长公共子序列长度；
  2. 转移方程：
    • 若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])；
  3. 初始条件：dp[0][j] = 0、dp[i][0] = 0（空字符串的LCS长度为0）；
  4. 遍历顺序：先i后j（或先j后i），从1到len(s1)/len(s2)。
为了方便初始化，一般会采用int[][] dp = new int[word1.length() + 1][word2.length() + 1]。其实我们可以理解为添加了字符串的长度为0的情况，也就是多了一个占位，所以dp[i][j]实际上表示的是字符串a的前i - 1个字符串b的前j - 1个（或者以此结尾）

例如经典的编辑距离问题：

classSolution{publicintminDistance(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]) + 1int[][] dp =newint[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()];}}
高频经典题
  1. LeetCode 1143. 最长公共子序列（LCS，基础模板）；
  2. LeetCode 300. 最长递增子序列（LIS，一维DP/贪心+二分）；
  3. LeetCode 72. 编辑距离（最值类子序列DP，后端文本处理场景）；
  4. LeetCode 516. 最长回文子序列（子序列DP，对称状态）。
避坑点
  1. 字符串索引偏移：dp[i][j]对应s1[i-1]、s2[j-1]，易误写为s1[i]、s2[j]导致越界；
  2. LIS的O(n²)优化：二刷需掌握贪心+二分的O(nlogn)解法（应对面试官追问）；
  3. 回文子序列初始条件：dp[i][i] = 1（单个字符是回文），而非0；
  4. 编辑距离转移方程遗漏：需考虑插入、删除、替换三种操作，避免漏项。

✅ 技巧四：区间DP（★★★ 占比10%+，进阶）

核心定位

状态与“区间[i,j]”相关，dp数组为二维，核心是“从小区间扩展到大全区间”，后端场景中对应“区间合并、字符串分割”。

核心原理
  • 状态定义：dp[i][j] = 区间[i,j]内的最优解（最值/方案数）；
  • 转移方程：dp[i][j] = f(dp[i][k], dp[k+1][j])（k为区间分割点，i≤k<j）；
  • 遍历顺序：先遍历区间长度（从2到n），再遍历区间起点i，终点j=i+len-1（保证小区间先计算）。
适用场景
  • 区间最值：石子合并、戳气球；
  • 回文类：最长回文子串（DP解法）、分割回文串II；
  • 字符串类：最长回文子序列（也可归为区间DP）。
核心思路（以最长回文子串为例）
  1. 状态定义：dp[i][j]表示字符串[i,j]是否是最长回文子串；
  2. 转移方程：dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1];
  3. 初始条件：dp数组的斜角表示单个字符，所以一定是回文的，全部初始化为true
  4. 遍历顺序：从下往上遍历，因为dp[i][j]依赖下面一行的数据
classSolution{publicStringlongestPalindrome(String s){//dp[i][j]表示字符串[i,j]是否是最长回文子串//dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]; boolean[][] dp =newboolean[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);}}
核心思路（以石子合并为例）
  1. 状态定义：dp[i][j] = 合并区间[i,j]的石子的最小代价；
  2. 转移方程：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j])（sum[i][j]为区间[i,j]石子和）；
  3. 初始条件：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]);}}}
高频经典题
  1. LeetCode 312. 戳气球（区间DP Hard级经典）；
  2. LeetCode 132. 分割回文串II（区间DP+贪心）；
  3. LeetCode 5. 最长回文子串（区间DP解法）。
避坑点
  1. 遍历顺序错误：先遍历起点再遍历长度，导致大全区间依赖的小区间未计算；
  2. 区间和未预处理：每次计算sum[i][j]用循环，时间复杂度升至O(n³)，需提前用前缀和数组；
  3. 初始条件错误：如戳气球中dp[i][j]初始化为0，导致最小值计算错误。

✅ 技巧五：树形DP（★★★ 占比10%+，后端场景关联）

核心定位

状态定义在树上，通过后序遍历（自底向上）计算子树的状态，后端场景中对应“树形结构的最值/方案数”（如公司人员分配、树的直径）。

核心原理
  • 状态定义：dp[node][0/1]代表“以node为根的子树，node选/不选时的最优解”；
  • 转移方程：通过后序遍历，合并左右子树的状态；
  • 遍历顺序：后序遍历（先计算左右子树，再计算根节点）。
适用场景
  • 树的最值：打家劫舍III（树形01背包）、二叉树的最大路径和；
  • 树形决策：员工的重要性、树的直径。
核心思路（以打家劫舍III为例）
  1. 状态定义：
    • dp[node][0]：不偷node时，子树的最大金额；
    • dp[node][1]：偷node时，子树的最大金额；
  2. 转移方程：
    • 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]；
  3. 初始条件：空节点dp[null][0] = dp[null][1] = 0；
  4. 遍历顺序：后序遍历递归计算。
高频经典题
  1. LeetCode 337. 打家劫舍III（树形DP核心模板）；
  2. LeetCode 124. 二叉树中的最大路径和（树形DP进阶）；
  3. LeetCode 543. 二叉树的直径（树形DP简单版）。
避坑点
  1. 递归终止条件遗漏：未处理空节点，导致空指针异常；
  2. 状态转移遗漏子树：如打家劫舍III中，未合并左右子树的状态；
  3. 重复计算子树状态：未用记忆化递归，导致时间复杂度升至O(2ⁿ)。

✅ 技巧六：状态压缩DP（★★ 占比10%+，优化核心）

核心定位

将多维状态（如二维）压缩为一维，或用二进制数表示状态（如集合），后端场景中对应“有限状态的优化”（如旅行商问题、状态压缩背包）。

核心原理
  • 二进制状态：用整数的二进制位表示“元素是否被选中”（如mask=5（101）代表第0、2个元素被选中）；
  • 转移方程：dp[mask] = f(dp[mask ^ (1<<i)])（mask为当前状态，i为选中的元素）；
  • 遍历顺序：遍历所有mask（从0到2ⁿ-1）。
适用场景
  • 集合类：旅行商问题（TSP）、子集状态压缩；
  • 多维压缩：二维DP→一维（如背包问题）、三维DP→二维。
核心思路（以TSP为例）
  1. 状态定义：dp[mask][i] = 访问过mask表示的城市，最后在城市i的最小路径；
  2. 转移方程：dp[mask][i] = min(dp[mask ^ (1<<i)][j] + dist[j][i])（j为前一个城市）；
  3. 初始条件：dp[1<<i][i] = 0（仅访问城市i，路径为0）；
  4. 遍历顺序：遍历mask（从1到2ⁿ-1），再遍历i，最后遍历j。
高频经典题
  1. LeetCode 698. 划分为k个相等的子集（状态压缩+回溯）；
  2. LeetCode 943. 最短超级串（状态压缩DP）；
  3. LeetCode 1986. 完成任务的最少工作时间段（状态压缩DP）。
避坑点
  1. 状态数爆炸：n>20时，2ⁿ>1e6，状态压缩不可行（需其他优化）；
  2. 二进制位操作错误：如1<<i易误写为1<<(i-1)，导致状态表示错误；
  3. 初始条件未初始化：如TSP中dp[mask][i]初始化为无穷大，未设置起点状态。

通用代码模板

✔ 模板1：DP通用模板（所有场景的基础）

// 通用DP模板（以二维DP为例）classDPGeneralTemplate{publicintdpTemplate(int[] nums1,int[] nums2){int n = nums1.length;int m = nums2.length;// 1. 状态定义：dp[i][j] 代表nums1前i个、nums2前j个的目标值int[][] dp =newint[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];}}

✔ 模板2：01背包（基础+空间优化，LeetCode 416. 分割等和子集）

classZeroOneKnapsack{// 题目：判断数组是否能分割为两个子集，和相等（01背包可行性）publicbooleancanPartition(int[] nums){int sum =0;for(int num : nums) sum += num;if(sum %2!=0)returnfalse;// 和为奇数，无法分割int target = sum /2;// 空间优化：一维dp，dp[j] = 容量j是否可达boolean[] dp =newboolean[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];}}

✔ 模板3：完全背包（基础+空间优化，LeetCode 518. 零钱兑换II）

classCompleteKnapsack{// 题目：给定金额和无限数量的硬币，求组成金额的组合数publicintchange(int amount,int[] coins){// 状态定义：dp[j] = 金额j的组合数int[] dp =newint[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];}}

✔ 模板4：最长递增子序列（LIS，LeetCode 300）

class LIS {// O(n²) DP解法 + O(nlogn) 贪心+二分优化publicintlengthOfLIS(int[] nums){int n = nums.length;if(n ==0)return0;// 1. O(n²) DP解法int[] dp =newint[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;}}

✔ 模板5：最长公共子序列（LCS，LeetCode 1143）

class LCS {publicintlongestCommonSubsequence(String text1,String text2){int n = text1.length();int m = text2.length();// 状态定义：dp[i][j] = text1前i个、text2前j个的LCS长度int[][] dp =newint[n+1][m+1];// 遍历顺序：先i后jfor(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];}}

✔ 模板6：树形DP（打家劫舍III，LeetCode 337）

classTreeDP{// 题目：二叉树中偷节点，不能偷相邻节点，求最大金额publicintrob(TreeNode root){int[] res =dfs(root);returnMath.max(res[0], res[1]);// 0：不偷根，1：偷根}// 后序遍历，返回int[2]：[不偷当前节点的最大值，偷当前节点的最大值]privateint[]dfs(TreeNode node){if(node ==null)returnnewint[]{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];returnnewint[]{notRob, rob};}// 二叉树节点定义staticclassTreeNode{int val;TreeNode left;TreeNode right;TreeNode(int x){ val = x;}}}

总结

动态规划二刷的核心逻辑（Java版）：

  1. 五要素是根基：状态定义→转移方程→初始条件→遍历顺序→空间优化，按此步骤解题，思路不混乱；
  2. 场景模板化：
    • 线性DP：一维数组，前序依赖；
    • 背包问题：二维→一维，注意遍历顺序；
    • 子序列DP：二维数组，字符匹配转移；
    • 区间DP：先长度后起点，分割点遍历；
    • 树形DP：后序遍历，子树状态合并；
  3. 优化是亮点：空间优化（滚动数组）、时间优化（贪心+二分）是超越普通候选人的关键；
  4. Java特性要注意：数组初始化、边界处理、大数取模，规避空指针和溢出。

✅ 高频避坑点（二刷必记）

  1. 状态定义模糊：写代码前先明确“dp[i][j]代表什么”，避免边写边改；
  2. 转移方程遗漏条件：如背包问题中未判断“j≥w[i]”，导致数组越界；
  3. 遍历顺序错误：
    • 01背包一维优化：容量逆序（否则重复选）；
    • 完全背包一维优化：容量正序；
    • 区间DP：先遍历长度再遍历起点；
  4. 初始条件错误：
    • 最值问题初始化为0（应初始化为MAX/MIN）；
    • 计数问题未初始化dp[0]=1；
  5. 空间优化时覆盖问题：如二维DP→一维时，未保留依赖的前序状态；
  6. 大数溢出：方案数问题未取模，导致int/long溢出；
  7. 忽略题目约束：如“子序列”vs“子串”，状态定义错误导致思路全错。

Read more

git2.53.0安装步骤

⭐ 一、安装（核心选项直接抄） 安装界面选择建议核心原因组件选择✅ 保留默认勾选，取消 Check daily for updates自动更新没必要，核心功能够用默认编辑器✅ 选 Use Visual Studio Code as Git's default editor避免 Vim 学习成本，和开发工具统一初始分支名✅ 选 Override，分支名填 main适配 GitHub/Gitee 主流规范PATH 配置✅ 选 Git from the command line and also from 3rd-party software多终端可用（Git Bash/CMD/VSCode）SSH 客户端✅

By Ne0inhk
使用 VS Code 将项目代码上传到 Gitee 的完整指南

使用 VS Code 将项目代码上传到 Gitee 的完整指南

在现代软件开发流程中，版本控制是不可或缺的一环。 Gitee（码云）作为国内领先的代码托管平台，为开发者提供了稳定、快速的 Git 服务。 本文将详细介绍如何使用 Visual Studio Code（VS Code）将本地项目代码上传至 Gitee 仓库，涵盖从环境配置、初始化仓库到推送代码的完整流程。 一、准备工作 1. 安装必要工具 * Git：确保你的系统已安装 Git。 可通过终端运行 git --version  或 git -v 验证是否安装成功。 * VS Code：下载并安装 Visual Studio Code。 * Gitee 账号：前往 Gitee 官网 注册账号（如尚未注册）。 2. 安装 VS

By Ne0inhk
最新Spring Security实战教程（十五）快速集成 GitHub 与 Gitee 的社交登录

最新Spring Security实战教程（十五）快速集成 GitHub 与 Gitee 的社交登录

🌷 古之立大事者，不惟有超世之才，亦必有坚忍不拔之志 🎐 个人CSND主页——Micro麦可乐的博客 🐥《Docker实操教程》专栏以最新的Centos版本为基础进行Docker实操教程，入门到实战 🌺《RabbitMQ》专栏19年编写主要介绍使用JAVA开发RabbitMQ的系列教程，从基础知识到项目实战 🌸《设计模式》专栏以实际的生活场景为案例进行讲解，让大家对设计模式有一个更清晰的理解 🌛《开源项目》本专栏主要介绍目前热门的开源项目，带大家快速了解并轻松上手使用 ✨《开发技巧》本专栏包含了各种系统的设计原理以及注意事项，并分享一些日常开发的功能小技巧 💕《Jenkins实战》专栏主要介绍Jenkins+Docker的实战教程，让你快速掌握项目CI/CD，是2024年最新的实战教程 🌞《Spring Boot》专栏主要介绍我们日常工作项目中经常应用到的功能以及技巧，代码样例完整 🌞《Spring Security》专栏中我们将逐步深入Spring Security的各个技术细节，带你从入门到精通，全面掌握这一安全技术 如果文章能够给大家带来一定的帮助！欢迎关注、评

By Ne0inhk

【2026最新收集】github国内镜像站，高速访问

一、最新可用GitHub镜像站汇总 以下镜像站经实测验证，按“直接访问型”“文件加速型”“知名项目专属型”分类，标注实时可用性，方便按需选择。 1. 直接访问型镜像站（可浏览仓库、查看代码） 此类镜像站完全复刻GitHub界面，支持搜索、浏览仓库、查看代码文件，操作逻辑与官网一致，适合日常代码查阅。 镜像站序号访问方式镜像站链接当前状态备注1直接访问https://bgithub.xyz✅ 可用界面简洁，响应速度快，支持仓库搜索2直接访问https://gitclone.com✅ 可用附带Git Clone加速命令，适合开发者使用3直接访问https://github.ur1.fun✅ 可用加载速度快，支持Markdown文档渲染 推荐场景：需在线浏览仓库结构、查看代码细节、复制代码片段时，优先选择bgithub.xyz或kkgithub.com，加载速度和稳定性最优。 2. 文件加速型镜像站（专用于下载Release、压缩包） 此类镜像站主打文件下载加速，无需浏览完整仓库，

By Ne0inhk