回溯 Backtrack可以把Backtracking 理解成 DFS 的一个特殊版本普通 DFS我沿着一条路走到底。Backtracking我沿着一条路走到底如果不满足条件就撤销选择换另一条路。1. Subsets子集子集题因为是单方向bootstrap的所以传索引但是不记录数字是否使用过比如LC78 SubsetsLC90 Subsets II核心choose - explore - unchoose2. Permutations排列排列题就需要记录数字是否使用过比如LC46 PermutationsLC47 Permutations II特点每次选择一个没用过的数字path [1,2] choose 3 path [1,2,3] backtrack remove 33. Combination组合比如LC77 CombinationsLC39 Combination Sum特点有选择范围start index避免重复。4. Partition分割比如LC131 Palindrome Partitioning比如aab [ [a,a,b], [aa,b] ]本质枚举切割位置。5. Search / Constraint Satisfaction搜索问题比如LC79 Word SearchLC51 N-Queens这种更像DFS Backtracking二分查找 Binary search普通二分找到了return mid因为 mid 就是答案。边界二分不断压缩范围return left因为最后left right 边界贪心算法 Greedy Algorithm每一步都选择当前最优的方案希望最后得到全局最优。比如你有硬币[1, 5, 10, 20]目标36如果硬币可以无限使用我们可以20 → 16 10 → 6 5 → 1 1 → 0于是20 10 5 1用了 4 枚。这就是贪心每次拿当前能拿的最大硬币。但注意贪心不是“看到最大就选最大”这么简单。因为很多问题里局部最优会导致全局最差。DP vs 贪心DP 我现在做这个选择会不会影响未来greedy: 我现在直接选一个我认为最好的之后不反悔。动态规划 Dynamic ProgrammingDP把一个大问题拆成很多相互关联的小问题把小问题的答案存下来避免重复计算。为什么叫“动态规划”比如你要算F(5)F(4)F(3)而 F(4)F(3)F(2)你会发现F(3) 被算了两次。如果继续往下展开会出现大量重复计算。DP 就是第一次算 F(3) → 把结果记下来第二次需要 F(3) → 直接拿之前的结果所以 DP 的核心其实就是重复子问题 保存已经算过的结果做题以后看到 DP 题主要问自己① State状态是什么dp[i]表示什么比如dp[i] 到达第 i 阶的方法数② Transition状态怎么转移当前状态怎么从之前的状态得到比如dp[i]dp[i−1]dp[i−2]③ Initialization初始状态是什么比如dp[1] 1 dp[2] 2④ Answer最后答案在哪里比如 return dp[n]Top-down DP递归 memoization记忆化Bottom-up DP从小问题开始一步步算到大问题模板class Solution: def xxx(self, n: int) - int: # 1. 定义 dp # dp[i] 表示__________ dp [0] * (n 1) # 2. 初始化 dp[0] ? dp[1] ? # 3. 状态转移 for i in range(2, n 1): dp[i] ? # 4. 返回答案 return dp[n]
回溯 Backtrack可以把Backtracking 理解成 DFS 的一个特殊版本普通 DFS我沿着一条路走到底。Backtracking我沿着一条路走到底如果不满足条件就撤销选择换另一条路。1. Subsets子集子集题因为是单方向bootstrap的所以传索引但是不记录数字是否使用过比如LC78 SubsetsLC90 Subsets II核心choose - explore - unchoose2. Permutations排列排列题就需要记录数字是否使用过比如LC46 PermutationsLC47 Permutations II特点每次选择一个没用过的数字path [1,2] choose 3 path [1,2,3] backtrack remove 33. Combination组合比如LC77 CombinationsLC39 Combination Sum特点有选择范围start index避免重复。4. Partition分割比如LC131 Palindrome Partitioning比如aab [ [a,a,b], [aa,b] ]本质枚举切割位置。5. Search / Constraint Satisfaction搜索问题比如LC79 Word SearchLC51 N-Queens这种更像DFS Backtracking二分查找 Binary search普通二分找到了return mid因为 mid 就是答案。边界二分不断压缩范围return left因为最后left right 边界贪心算法 Greedy Algorithm每一步都选择当前最优的方案希望最后得到全局最优。比如你有硬币[1, 5, 10, 20]目标36如果硬币可以无限使用我们可以20 → 16 10 → 6 5 → 1 1 → 0于是20 10 5 1用了 4 枚。这就是贪心每次拿当前能拿的最大硬币。但注意贪心不是“看到最大就选最大”这么简单。因为很多问题里局部最优会导致全局最差。DP vs 贪心DP 我现在做这个选择会不会影响未来greedy: 我现在直接选一个我认为最好的之后不反悔。动态规划 Dynamic ProgrammingDP把一个大问题拆成很多相互关联的小问题把小问题的答案存下来避免重复计算。为什么叫“动态规划”比如你要算F(5)F(4)F(3)而 F(4)F(3)F(2)你会发现F(3) 被算了两次。如果继续往下展开会出现大量重复计算。DP 就是第一次算 F(3) → 把结果记下来第二次需要 F(3) → 直接拿之前的结果所以 DP 的核心其实就是重复子问题 保存已经算过的结果做题以后看到 DP 题主要问自己① State状态是什么dp[i]表示什么比如dp[i] 到达第 i 阶的方法数② Transition状态怎么转移当前状态怎么从之前的状态得到比如dp[i]dp[i−1]dp[i−2]③ Initialization初始状态是什么比如dp[1] 1 dp[2] 2④ Answer最后答案在哪里比如 return dp[n]Top-down DP递归 memoization记忆化Bottom-up DP从小问题开始一步步算到大问题模板class Solution: def xxx(self, n: int) - int: # 1. 定义 dp # dp[i] 表示__________ dp [0] * (n 1) # 2. 初始化 dp[0] ? dp[1] ? # 3. 状态转移 for i in range(2, n 1): dp[i] ? # 4. 返回答案 return dp[n]
