回溯算法与动态规划核心知识点及 Java 实现总结 | 极客日志

Javajava算法

回溯算法与动态规划核心知识点及 Java 实现总结

综述由AI生成总结了回溯算法与动态规划的核心知识点及 Java 实现。回溯部分涵盖组合、排列、子集、切割、棋盘五大场景，强调 startIndex 与 used 数组的区别、剪枝优化及去重技巧。动态规划部分详解线性 DP、背包问题（01/完全/分组）、子序列/子串 DP、区间 DP、树形 DP 及状态压缩 DP，重点讲解状态定义、转移方程、初始条件、遍历顺序及空间优化。文章提供通用代码模板与高频 LeetCode 例题，适合后端面试准备。

星星泡饭发布于 2026/3/25更新于 2026/5/1219 浏览

回溯算法部分

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

核心知识点

✅ 核心定义与本质

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

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

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

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

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

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

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

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

✅ 回溯与递归/DFS 的关系

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

技巧方法

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

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

维度	组合问题	排列问题
核心本质	从 `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`）

去重步骤	组合问题（如组合总和 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` 则是同一路径的上一个元素） - 跳过同一层重复元素，避免生成重复排列
核心原理	同一层中，相同元素只选第一个，后续的跳过	同一层中，相同元素若前一个未被选，则当前元素跳过（避免重复）

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; // 恢复标记（回溯）
        }
    }
}

// 通用回溯模板（以组合问题为例）
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 实现方式
状态定义	定义 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 数组维度（如二维→一维），减少空间复杂度（后端面试高频追问）	滚动数组、逆序遍历、变量替代数组

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

// 一维优化版
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]);
    }
}

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]);
    }
}

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()];
    }
}

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);
    }
}

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 模板（以二维 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; }
    }
}