算法

核心算法范式

本仓库实现了多种核心算法范式来解决不同类型的问题。理解这些范式对于系统性地解决 LeetCode 问题至关重要。

来源：[thinkings/dynamic-programming.md:1-939]

回溯

回溯是一种系统性的方法，通过逐步构建候选解并弃掉无效解来探索所有可能的解。它尤其适用于组合问题。

回溯的关键特性

使用递归逐步构建解
提前放弃无效路径（剪枝）
通常用递归树表示
常见的模板模式遵循选择-探索-取消选择的流程

回溯问题模板

常见的回溯问题包括

排列 [problems/46.permutations.md:61-145]
有重复元素的排列 [problems/47.permutations-ii.md:72-100]
子集 [problems/78.subsets.md:58-75]
组合 [problems/39.combination-sum.md:84-108]

来源：[problems/46.permutations.md:35-45], [problems/47.permutations-ii.md:33-53], [problems/78.subsets.md:39-50], [problems/39.combination-sum.md:55-70]

动态规划

动态规划 (DP) 是一种将复杂问题分解为简单的重叠子问题，并且只解决每个子问题一次的方法。

动态规划的核心要素是

状态定义：DP 问题的关键在于正确定义每个状态代表的含义。例如
- 一维数组：dp[i] 表示前 i 个元素的某种属性
- 二维数组：dp[i][j] 表示两个变量之间的关系
基本情况：建立可以直接解决的最简单的子问题。
状态转移：定义如何从较小的解构建较大解的公式。
实现方法:
- 记忆化（自顶向下）：使用带缓存的递归来避免重复计算
- 制表（自底向上）：迭代地从最小到最大的构建解
空间优化：滚动数组等技术以减少内存使用

示例：找零问题

问题要求找到制作特定金额所需的最小硬币数量。

状态定义：dp[i] = 制作金额 i 所需的最小硬币数量

来源：[thinkings/dynamic-programming.md:195-934], [problems/322.coin-change.md:61-226], [problems/518.coin-change-2.md:50-172], [problems/198.house-robber.md:52-97]

树算法

树遍历是解决基于树的问题的基本操作。本仓库实现了几种遍历方法。

深度优先搜索 (DFS)

深度优先搜索 (DFS) 在回溯之前尽可能深地遍历每个分支。它可以递归或迭代实现。

DFS 模板（递归）

使用双色标记的统一迭代 DFS

该技术为迭代实现所有三种 DFS 遍历顺序提供了一种统一的方法

通过调整推入堆栈的项的顺序，可以实现前序、中序或后序遍历。

来源：[thinkings/tree.md:152-227], [thinkings/tree.md:254-326], [thinkings/tree.md:385-399]

广度优先搜索 (BFS)

广度优先搜索 (BFS) 按层遍历树，这对于查找最短路径或与层相关的操作很有用。

带层信息的 BFS

不带层信息的 BFS

来源：[thinkings/tree.md:402-507]

算法应用模式

本仓库将树问题分为三种主要类型

问题解决技术

在处理算法问题时，本仓库采用了一些关键技术

状态定义和转移：对于动态规划至关重要，定义每个状态的含义以及状态之间的关系。
带记忆化的递归：通过缓存重叠子问题的结果来优化递归解。
空间优化：使用滚动数组等技术来减少动态规划中的内存使用。
树遍历变体：调整标准遍历方法以解决特定问题。
带剪枝的回溯：通过提前消除无效路径来提高回溯效率。

这些技术如何映射到问题类型

技术	问题类型	示例
回溯	组合、排列、子集	[problems/46.permutations.md]
动态规划 (一维)	序列优化	[problems/198.house-robber.md]
动态规划 (二维)	网格/双序列问题	[problems/322.coin-change.md]
树 DFS	路径查找、树属性	[thinkings/tree.md]
树 BFS	层序操作、最短路径	[thinkings/tree.md]

来源：[thinkings/dynamic-programming.md:239-421], [thinkings/tree.md:516-736]

优化技术

本仓库展示了几种算法实现优化技术

动态规划中的空间优化

将二维 DP 问题转化为仅使用一维空间（滚动数组技术）

来源：[problems/322.coin-change.md:167-226], [thinkings/dynamic-programming.md:629-652]

递归的记忆化

使用记忆化优化递归解

来源：[thinkings/dynamic-programming.md:154-166]

带剪枝的高效回溯

避免不必要探索的剪枝技术

来源：[problems/40.combination-sum-ii.md:84-201]

算法实现

本节将算法概念与它们在仓库代码库中的实现联系起来。

动态规划实现

本仓库遵循以下步骤实现动态规划解

状态定义
识别基本情况
开发状态转移公式
决定采用自顶向下还是自底向上方法
实现并可能进行空间优化

来自硬币找零问题的示例

来源：[problems/322.coin-change.md:211-221], [thinkings/dynamic-programming.md:774-935]

回溯实现

本仓库使用此通用模式实现回溯解

仓库中的示例包括

排列 [problems/46.permutations.md]
子集 [problems/78.subsets.md]
组合总和 [problems/39.combination-sum.md]

来源：[problems/46.permutations.md:58-78], [problems/78.subsets.md:58-89], [problems/39.combination-sum.md:84-108]

总结

本文档涵盖了仓库中使用的核心算法，重点关注

核心算法范式：回溯、动态规划和树遍历
实现模式：这些算法在代码中的结构
优化技术：空间缩减、记忆化和剪枝
问题类别：不同问题类型如何映射到算法方法

理解这些基本算法及其实现，为应对本仓库中的各种 LeetCode 问题奠定了基础。

有关更具体的算法应用，请参阅 problems/ 目录中的各个问题解决方案以及 thinkings/ 目录中的详细算法解释。

来源：[thinkings/dynamic-programming.md], [thinkings/tree.md], [problems/46.permutations.md], [problems/47.permutations-ii.md], [problems/78.subsets.md], [problems/90.subsets-ii.md], [problems/39.combination-sum.md], [problems/40.combination-sum-ii.md], [problems/322.coin-change.md], [problems/518.coin-change-2.md], [problems/198.house-robber.md]

算法