Zxy's Blog

完全背包问题 在本节中，我们先求解另一个常见的背包问题：完全背包，再了解它的一种特例：零钱兑换。 完全背包问题 question 给定 $n$ 个物品，第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$ ，和一个容量为 $cap$ 的背包。**每个物品可以重复选取**，问在限定背包容量下能放入物品的最大价值。示例如下图所示。 动态规划思路 完全背包问题和 0-1 背包问题非常相似，区别仅在于不限制物品的选择次数。 在 0-1 背包问题中，每种物品只有一个，因此将物品 iii 放入背包后，只能从前 i−1i-1i−1 个物品中选择。 在完全背包问题中，每种物品的数量是无限的，因此将物品 iii 放入背包后，仍可以从前 iii 个物品中选择。 在完全背包问题的规定下，状态 [i,c][i, c][i,c] 的变化分为两种情况。 不放入物品 iii ：与 0-1 背包问题相同，转移至 [i−1,c][i-1, c][i−1,c] 。 放入物品 iii ：与 0-1 背包问题不同，转移至 [i,c−wgt[i−1]][i,...

0-1 背包问题 背包问题是一个非常好的动态规划入门题目，是动态规划中最常见的问题形式。其具有很多变种，例如 0-1 背包问题、完全背包问题、多重背包问题等。 在本节中，我们先来求解最常见的 0-1 背包问题。 question 给定 $n$ 个物品，第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$ ，和一个容量为 $cap$ 的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。 观察下图，由于物品编号 iii 从 111 开始计数，数组索引从 000 开始计数，因此物品 iii 对应重量 wgt[i−1]wgt[i-1]wgt[i−1] 和价值 val[i−1]val[i-1]val[i−1] 。 我们可以将 0-1 背包问题看作一个由 nnn 轮决策组成的过程，对于每个物体都有不放入和放入两种决策，因此该问题满足决策树模型。 该问题的目标是求解“在限定背包容量下能放入物品的最大价值”，因此较大概率是一个动态规划问题。 第一步：思考每轮的决策，定义状态，从而得到 dpdpdp...

...

动态规划问题特性 在上一节中，我们学习了动态规划是如何通过子问题分解来求解原问题的。实际上，子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点不同。 分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。 动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。 回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题。 实际上，动态规划常用来求解最优化问题，它们不仅包含重叠子问题，还具有另外两大特性：最优子结构、无后效性。 最优子结构 我们对爬楼梯问题稍作改动，使之更加适合展示最优子结构概念。 question “爬楼梯最小代价” 给定一个楼梯，你每步可以上 $1$ 阶或者 $2$ 阶，每一阶楼梯上都贴有一个非负整数，表示你在该台阶所需要付出的代价。给定一个非负整数数组 $cost$ ，其中 $cost[i]$ 表示在第 $i$...

初探动态规划 动态规划（dynamic programming）是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。 在本节中，我们从一个经典例题入手，先给出它的暴力回溯解法，观察其中包含的重叠子问题，再逐步导出更高效的动态规划解法。 question “爬楼梯” 给定一个共有 $n$ 阶的楼梯，你每步可以上 $1$ 阶或者 $2$ 阶，请问有多少种方案可以爬到楼顶？ 如下图所示，对于一个 333 阶楼梯，共有 333 种方案可以爬到楼顶。 本题的目标是求解方案数量，我们可以考虑通过回溯来穷举所有可能性。具体来说，将爬楼梯想象为一个多轮选择的过程：从地面出发，每轮选择上 111 阶或 222 阶，每当到达楼梯顶部时就将方案数量加 111 ，当越过楼梯顶部时就将其剪枝。代码如下所示： 12345678910111213141516171819202122def backtrack(choices: list[int], state: int, n: int, res: list[int]) ->...

...

n 皇后问题 question 根据国际象棋的规则，皇后可以攻击与同处一行、一列或一条斜线上的棋子。给定 $n$ 个皇后和一个 $n \times n$ 大小的棋盘，寻找使得所有皇后之间无法相互攻击的摆放方案。 如下图所示，当 n=4n = 4n=4 时，共可以找到两个解。从回溯算法的角度看，n×nn \times nn×n 大小的棋盘共有 n2n^2n2 个格子，给出了所有的选择 choices 。在逐个放置皇后的过程中，棋盘状态在不断地变化，每个时刻的棋盘就是状态 state 。 下图展示了本题的三个约束条件：多个皇后不能在同一行、同一列、同一条对角线上。值得注意的是，对角线分为主对角线 \ 和次对角线 / 两种。 逐行放置策略 皇后的数量和棋盘的行数都为 nnn ，因此我们容易得到一个推论：棋盘每行都允许且只允许放置一个皇后。 也就是说，我们可以采取逐行放置策略：从第一行开始，在每行放置一个皇后，直至最后一行结束。 下图所示为 4...

子集和问题 无重复元素的情况 question 给定一个正整数数组 `nums` 和一个目标正整数 `target` ，请找出所有可能的组合，使得组合中的元素和等于 `target` 。给定数组无重复元素，每个元素可以被选取多次。请以列表形式返回这些组合，列表中不应包含重复组合。 例如，输入集合 {3,4,5}\{3, 4, 5\}{3,4,5} 和目标整数 999 ，解为 {3,3,3},{4,5}\{3, 3, 3\}, \{4, 5\}{3,3,3},{4,5} 。需要注意以下两点。 输入集合中的元素可以被无限次重复选取。 子集不区分元素顺序，比如 {4,5}\{4, 5\}{4,5} 和 {5,4}\{5, 4\}{5,4} 是同一个子集。 参考全排列解法 类似于全排列问题，我们可以把子集的生成过程想象成一系列选择的结果，并在选择过程中实时更新“元素和”，当元素和等于 target 时，就将子集记录至结果列表。 而与全排列问题不同的是，本题集合中的元素可以被无限次选取，因此无须借助 selected...

全排列问题 全排列问题是回溯算法的一个典型应用。它的定义是在给定一个集合（如一个数组或字符串）的情况下，找出其中元素的所有可能的排列。 下表列举了几个示例数据，包括输入数组和对应的所有排列。 表   全排列示例 输入数组 所有排列 [1][1][1] [1][1][1] [1,2][1, 2][1,2] [1,2],[2,1][1, 2], [2, 1][1,2],[2,1] [1,2,3][1, 2, 3][1,2,3] [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1][1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1][1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] 无相等元素的情况 question 输入一个整数数组，其中不包含重复元素，返回所有可能的排列。 从回溯算法的角度看，我们可以把生成排列的过程想象成一系列选择的结果。假设输入数组为...

回溯算法 回溯算法（backtracking algorithm）是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。 回溯算法通常采用“**深度优先搜索**”来遍历解空间。在“二叉树”章节中，我们提到前序、中序和后序遍历都属于深度优先搜索。接下来，我们利用前序遍历构造一个回溯问题，逐步了解回溯算法的工作原理。 “例题一” 给定一棵二叉树，搜索并记录所有值为 $7$ 的节点，请返回节点列表。 对于此题，我们前序遍历这棵树，并判断当前节点的值是否为 777 ，若是，则将该节点的值加入结果列表 res 之中。相关过程实现如下图和以下代码所示： 12345678910def pre_order(root: TreeNode): """前序遍历：例题一""" if root is None: # 该节点为None，返回父节点 return if...