自已建网站微信登录,wordpress 更改模板路径,新乡seo网站推广工具,做网站渠道数据结构之---- 动态规划
什么是动态规划#xff1f;
动态规划是一个重要的算法范式#xff0c;它将一个问题分解为一系列更小的子问题#xff0c;并通过存储子问题的解来避免重复计算#xff0c;从而大幅提升时间效率。
在本节中#xff0c;我们从一个经典例题入手
动态规划是一个重要的算法范式它将一个问题分解为一系列更小的子问题并通过存储子问题的解来避免重复计算从而大幅提升时间效率。
在本节中我们从一个经典例题入手先给出它的暴力回溯解法观察其中包含的重叠子问题再逐步导出更高效的动态规划解法。
爬楼梯给定一个共有 阶的楼梯你每步可以上 1 阶或者 2 阶请问有多少种方案可以爬到楼顶。
如图所示对于一个 3 阶楼梯共有 3 种方案可以爬到楼顶。 本题的目标是求解方案数量我们可以考虑通过回溯来穷举所有可能性。 具体来说将爬楼梯想象为一个多轮选择的过程 从地面出发每轮选择上 1 阶或 2 阶每当到达楼梯顶部时就将方案数量加 1 当越过楼梯顶部时就将其剪枝。
/* 回溯 */
void backtrack(ListInteger choices, int state, int n, ListInteger res) {// 当爬到第 n 阶时方案数量加 1if (state n)res.set(0, res.get(0) 1);// 遍历所有选择for (Integer choice : choices) {// 剪枝不允许越过第 n 阶if (state choice n)break;// 尝试做出选择更新状态backtrack(choices, state choice, n, res);// 回退}
}/* 爬楼梯回溯 */
int climbingStairsBacktrack(int n) {ListInteger choices Arrays.asList(1, 2); // 可选择向上爬 1 或 2 阶int state 0; // 从第 0 阶开始爬ListInteger res new ArrayList();res.add(0); // 使用 res[0] 记录方案数量backtrack(choices, state, n, res);return res.get(0);
}方法一暴力搜索
回溯算法通常并不显式地对问题进行拆解而是将问题看作一系列决策步骤通过试探和剪枝搜索所有可能的解。
我们可以尝试从问题分解的角度分析这道题。 设爬到第 阶共有 [ ] 种方案那么 [ ] 就是原问题其子问题包括: 由于每轮只能上 1 阶或 2 阶因此当我们站在第 阶楼梯上时上一轮只可能站在第 − 1 阶或第 − 2 阶上。 换句话说我们只能从第 − 1 阶或第 − 2 阶前往第 阶。 由此便可得出一个重要推论爬到第 − 1 阶的方案数加上爬到第 − 2 阶的方案数就等于爬到第 阶的方案数。 公式如下 这意味着在爬楼梯问题中各个子问题之间存在递推关系原问题的解可以由子问题的解构建得来。 下图展示了该递推关系。 我们可以根据递推公式得到暴力搜索解法。以 [ ] 为起始点递归地将一个较大问题拆解为两个较小问题的和直至到达最小子问题 [ 1 ] 和 [ 2 ] 时返回。 其中最小子问题的解是已知的即 [ 1 ] 1、 [ 2 ] 2 表示爬到第 1、2 阶分别有 1、2 种方案。 观察以下代码它和标准回溯代码都属于深度优先搜索但更加简洁。
/* 搜索 */
int dfs(int i) {// 已知 dp[1] 和 dp[2] 返回之if (i 1 || i 2)return i;// dp[i] dp[i-1] dp[i-2]int count dfs(i - 1) dfs(i - 2);return count;
}/* 爬楼梯搜索 */
int climbingStairsDFS(int n) {return dfs(n);
}下图展示了暴力搜索形成的递归树。对于问题 [ ] 其递归树的深度为 时间复杂度为 (2) 。指数阶属于爆炸式增长如果我们输入一个比较大的 则会陷入漫长的等待之中。 观察上图指数阶的时间复杂度是由于 重叠子问题导致的。 例如 [ 9 ] 被分解为 [ 8 ] 和 [ 7 ] [ 8 ] 被分解为 [ 7 ] 和 [ 6 ] 两者都包含子问题 [ 7 ] 。 以此类推子问题中包含更小的重叠子问题子子孙孙无穷尽也。绝大部分计算资源都浪费在这些重叠的问题上。
方法二记忆化搜索
为了提升算法效率我们希望所有的重叠子问题都只被计算一次。为此我们声明一个数组 mem 来记录每个子问题的解并在搜索过程中将重叠子问题剪枝。
当首次计算 [ ] 时我们将其记录至 mem [ i ] 以便之后使用。当再次需要计算 [ ] 时我们便可直接从 mem [ i ] 中获取结果从而避免重复计算该子问题。
/* 记忆化搜索 */
int dfs(int i, int[] mem) {// 已知 dp[1] 和 dp[2] 返回之if (i 1 || i 2)return i;// 若存在记录 dp[i] 则直接返回之if (mem[i] ! -1)return mem[i];// dp[i] dp[i-1] dp[i-2]int count dfs(i - 1, mem) dfs(i - 2, mem);// 记录 dp[i]mem[i] count;return count;
}/* 爬楼梯记忆化搜索 */
int climbingStairsDFSMem(int n) {// mem[i] 记录爬到第 i 阶的方案总数-1 代表无记录int[] mem new int[n 1];Arrays.fill(mem, -1);return dfs(n, mem);
}观察下图经过记忆化处理后所有重叠子问题都只需被计算一次时间复杂度被优化至 () 这是一个巨大的飞跃。 方法三动态规划
记忆化搜索是一种“从顶至底”的方法我们从原问题根节点开始递归地将较大子问题分解为较小子问题直至解已知的最小子问题叶节点。 之后通过回溯将子问题的解逐层收集构建出原问题的解。
与之相反动态规划是一种“从底至顶”的方法从最小子问题的解开始迭代地构建更大子问题的解直至得到原问题的解。
由于动态规划不包含回溯过程因此只需使用循环迭代实现无须使用递归。 在以下代码中我们初始化一个数组 dp 来存储子问题的解它起到了记忆化搜索中数组 mem 相同的记录作用。
/* 爬楼梯动态规划 */
int climbingStairsDP(int n) {if (n 1 || n 2)return n;// 初始化 dp 表用于存储子问题的解int[] dp new int[n 1];// 初始状态预设最小子问题的解dp[1] 1;dp[2] 2;// 状态转移从较小子问题逐步求解较大子问题for (int i 3; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];
}下图模拟了以上代码的执行过程。 与回溯算法一样动态规划也使用 状态 概念来表示问题求解的某个特定阶段每个状态都对应一个子问题以及相应的局部最优解。 例如爬楼梯问题的状态定义为当前所在楼梯阶数 。 根据以上内容我们可以总结出动态规划的常用术语。
将数组 dp 称为「 表」[] 表示状态 对应子问题的解。将最小子问题对应的状态即第 1 和 2 阶楼梯称为「初始状态」。将递推公式 [] [ − 1] [ − 2] 称为「状态转移方程」。
空间优化
细心的你可能发现由于 [ ] 只与 [ − 1 ] 和 [ − 2 ] 有关因此我们无须使用一个数组 dp 来存储所有子问题的解而只需两个变量滚动前进即可。
/* 爬楼梯空间优化后的动态规划 */
int climbingStairsDPComp(int n) {if (n 1 || n 2)return n;int a 1, b 2;for (int i 3; i n; i) {int tmp b;b a b;a tmp;}return b;
}观察以上代码由于省去了数组 dp 占用的空间因此空间复杂度从 () 降低至 (1) 。
在动态规划问题中当前状态往往仅与前面有限个状态有关这时我们可以只保留必要的状态通过 降维 来节省内存空间。 这种空间优化技巧被称为“滚动变量”或“滚动数组”。
动态规划问题特性
在上节中我们学习了动态规划是如何通过子问题分解来求解问题的。实际上子问题分解是一种通用的算法思路在分治、动态规划、回溯中的侧重点不同。
分治算法递归地将原问题划分为多个相互独立的子问题直至最小子问题并在回溯中合并子问题的解最终得到原问题的解。动态规划也对问题进行递归分解但与分治算法的主要区别是动态规划中的子问题是相互依赖的在分解过程中会出现许多重叠子问题。回溯算法在尝试和回退中穷举所有可能的解并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成我们可以将每个决策步骤之前的子序列看作为一个子问题。
实际上动态规划常用来求解最优化问题它们不仅包含重叠子问题还具有另外两大特性最优子结构、无后效性。
最优子结构
我们对爬楼梯问题稍作改动使之更加适合展示最优子结构概念。
爬楼梯最小代价 给定一个楼梯你每步可以上 1 阶或者 2 阶每一阶楼梯上都贴有一个非负整数表示你在该台阶所需要付出的代价。给定一个非负整数数组 其中 [ ] 表示在第 个台阶需要付出的代价 [ 0 ] 为地面起始点。 请计算最少需要付出多少代价才能到达顶部
如图所示若第 1、2、3 阶的代价分别为 1、10、1 则从地面爬到第 3 阶的最小代价为 2 。 设 [ ] 为爬到第 阶累计付出的代价由于第 阶只可能从 − 1 阶或 − 2 阶走来因此 [ ] 只可能等于 [ −1 ] [ ] 或 [ −2 ] [ ] 。为了尽可能减少代价我们应该选择两者中较小的那一个 这便可以引出最优子结构的含义原问题的最优解是从子问题的最优解构建得来的。
本题显然具有最优子结构我们从两个子问题最优解 [ − 1 ] 和 [ − 2 ] 中挑选出较优的那一个并用它构建出原问题 [ ] 的最优解。
那么上节的爬楼梯题目有没有最优子结构呢 它的目标是求解方案数量看似是一个计数问题但如果换一种问法 求解最大方案数量 。 我们意外地发现虽然题目修改前后是等价的但最优子结构浮现出来了 第 阶最大方案数量等于第 − 1 阶和第 − 2 阶最大方案数量之和。 所以说最优子结构的解释方式比较灵活在不同问题中会有不同的含义。 根据状态转移方程以及初始状态 [ 1 ] [ 1 ] 和 [ 2 ] [ 2 ] 我们就可以得到动态规划代码。
/* 爬楼梯最小代价动态规划 */
int minCostClimbingStairsDP(int[] cost) {int n cost.length - 1;if (n 1 || n 2)return cost[n];// 初始化 dp 表用于存储子问题的解int[] dp new int[n 1];// 初始状态预设最小子问题的解dp[1] cost[1];dp[2] cost[2];// 状态转移从较小子问题逐步求解较大子问题for (int i 3; i n; i) {dp[i] Math.min(dp[i - 1], dp[i - 2]) cost[i];}return dp[n];
}下图展示了以上代码的动态规划过程。 本题也可以进行空间优化将一维压缩至零维使得空间复杂度从 () 降低至 (1) 。
/* 爬楼梯最小代价空间优化后的动态规划 */
int minCostClimbingStairsDPComp(int[] cost) {int n cost.length - 1;if (n 1 || n 2)return cost[n];int a cost[1], b cost[2];for (int i 3; i n; i) {int tmp b;b Math.min(a, tmp) cost[i];a tmp;}return b;
}无后效性
无后效性是动态规划能够有效解决问题的重要特性之一定义为给定一个确定的状态它的未来发展只与当前状态有关而与当前状态过去所经历过的所有状态无关。
以爬楼梯问题为例给定状态 它会发展出状态 1 和状态 2 分别对应跳 1 步和跳 2 步。在做出这两种选择时我们无须考虑状态 之前的状态它们对状态 的未来没有影响。 然而如果我们向爬楼梯问题添加一个约束情况就不一样了。
带约束爬楼梯 给定一个共有 阶的楼梯你每步可以上 1 阶或者 2 阶但不能连续两轮跳 1 阶请问有多少种方案可以爬到楼顶。
例如图所示爬上第 3 阶仅剩 2 种可行方案其中连续三次跳 1 阶的方案不满足约束条件因此被舍弃。 在该问题中如果上一轮是跳 1 阶上来的那么下一轮就必须跳 2 阶。这意味着下一步选择不能由当前状态当前楼梯阶数独立决定还和前一个状态上轮楼梯阶数有关。 不难发现此问题已不满足无后效性状态转移方程 [ ] [ − 1 ] [ − 2 ] 也失效了因为 [ − 1 ] 代表本轮跳 1 阶但其中包含了许多 上一轮跳 1 阶上来的 方案而为了满足约束我们就不能将 [ − 1 ] 直接计入 [ ] 中。
为此我们需要扩展状态定义状态 [ , ] 表示处在第 阶、并且上一轮跳了 阶其中 ∈ { 1, 2 } 。此状态定义有效地区分了上一轮跳了 1 阶还是 2 阶我们可以据此来判断当前状态是从何而来的。
当上一轮跳了 1 阶时上上一轮只能选择跳 2 阶即 [ , 1 ] 只能从 [ − 1, 2 ] 转移过来。当上一轮跳了 2 阶时上上一轮可选择跳 1 阶或跳 2 阶即 [ , 2 ] 可以从 [ −2, 1 ] 或 [ −2, 2 ]转移过来。
如图所示在该定义下 [ , ] 表示状态 [ , ] 对应的方案数。此时状态转移方程为 最终返回 [ , 1 ] [ , 2 ] 即可两者之和代表爬到第 阶的方案总数。
/* 带约束爬楼梯动态规划 */
int climbingStairsConstraintDP(int n) {if (n 1 || n 2) {return 1;}// 初始化 dp 表用于存储子问题的解int[][] dp new int[n 1][3];// 初始状态预设最小子问题的解dp[1][1] 1;dp[1][2] 0;dp[2][1] 0;dp[2][2] 1;// 状态转移从较小子问题逐步求解较大子问题for (int i 3; i n; i) {dp[i][1] dp[i - 1][2];dp[i][2] dp[i - 2][1] dp[i - 2][2];}return dp[n][1] dp[n][2];
}在上面的案例中由于仅需多考虑前面一个状态我们仍然可以通过扩展状态定义使得问题重新满足无后效性。然而某些问题具有非常严重的 有后效性 。
爬楼梯与障碍生成 给定一个共有 阶的楼梯你每步可以上 1 阶或者 2 阶。规定当爬到第 阶时系统自动会给第 2 阶上放上障碍物之后所有轮都不允许跳到第 2 阶上。 例如前两轮分别跳到了第 2、3 阶上则之后就不能跳到第 4、6 阶上。 请问有多少种方案可以爬到楼顶。
在这个问题中下次跳跃依赖于过去所有的状态因为每一次跳跃都会在更高的阶梯上设置障碍并影响未来的跳跃。对于这类问题动态规划往往难以解决。
实际上许多复杂的组合优化问题例如旅行商问题都不满足无后效性。 对于这类问题我们通常会选择使用其他方法例如启发式搜索、遗传算法、强化学习等从而在有限时间内得到可用的局部最优解。
动态规划解题思路
上面介绍了动态规划问题的主要特征接下来我们一起探究两个更加实用的问题。
如何判断一个问题是不是动态规划问题求解动态规划问题该从何处入手完整步骤是什么
问题判断
总的来说如果一个问题包含重叠子问题、最优子结构并满足无后效性那么它通常就适合用动态规划求解。 然而我们很难从问题描述上直接提取出这些特性。因此我们通常会放宽条件先观察问题是否适合使用回溯穷举解决。
适合用回溯解决的问题通常满足“决策树模型”这种问题可以使用树形结构来描述其中每一个节点代表一个决策每一条路径代表一个决策序列。
换句话说如果问题包含明确的决策概念并且解是通过一系列决策产生的那么它就满足决策树模型通常可以使用回溯来解决。
在此基础上动态规划问题还有一些判断的加分项。
问题包含最大小或最多少等最优化描述。问题的状态能够使用一个列表、多维矩阵或树来表示并且一个状态与其周围的状态存在递推关系。相应地也存在一些 减分项 。问题的目标是找出所有可能的解决方案而不是找出最优解。问题描述中有明显的排列组合的特征需要返回具体的多个方案。
如果一个问题满足决策树模型并具有较为明显的 加分项 我们就可以假设它是一个动态规划问题并在求解过程中验证它。
问题求解步骤
动态规划的解题流程会因问题的性质和难度而有所不同但通常遵循以下步骤描述决策定义状态建立 表推导状态转移方程确定边界条件等。
为了更形象地展示解题步骤我们使用一个经典问题 最小路径和 来举例。
问题 给定一个 × 的二维网格 grid 网格中的每个单元格包含一个非负整数表示该单元格的代价。机器人以左上角单元格为起始点每次只能向下或者向右移动一步直至到达右下角单元格。请返回从左上角到右下角的最小路径和。
下图展示了一个例子给定网格的最小路径和为 13 。 第一步思考每轮的决策定义状态从而得到 表
本题的每一轮的决策就是从当前格子向下或向右一步。设当前格子的行列索引为 [ , ] 则向下或向右走一步后索引变为 [ 1, ] 或 [ , 1 ] 。因此状态应包含行索引和列索引两个变量记为 [ , ] 。
状态 [ , ] 对应的子问题为从起始点 [ 0, 0 ] 走到 [ , ] 的最小路径和解记为 [ , ] 。 至此我们就得到了下图所示的二维 矩阵其尺寸与输入网格 相同。 动态规划和回溯过程可以被描述为一个决策序列而状态由所有决策变量构成。 它应当包含描述解题进度的所有变量其包含了足够的信息能够用来推导出下一个状态。
每个状态都对应一个子问题我们会定义一个 表来存储所有子问题的解状态的每个独立变量都是 表的一个维度。本质上看 表是状态和子问题的解之间的映射。
第二步找出最优子结构进而推导出状态转移方程 对于状态 [ , ] 它只能从上边格子 [ − 1, ] 和左边格子 [ , − 1 ] 转移而来。 因此最优子结构为到达[ , ] 的最小路径和由 [ , − 1 ] 的最小路径和与 [ − 1, ] 的最小路径和这两者较小的那一个决定。 根据以上分析可推出下图所示的状态转移方程 根据定义好的 表思考原问题和子问题的关系找出通过子问题的最优解来构造原问题的最优解的方法即最优子结构。 一旦我们找到了最优子结构就可以使用它来构建出状态转移方程。
第三步确定边界条件和状态转移顺序
在本题中首行的状态只能从其左边的状态得来首列的状态只能从其上边的状态得来因此首行 0 和首列 0 是边界条件。
如图所示由于每个格子是由其左方格子和上方格子转移而来因此我们使用采用循环来遍历矩阵外循环遍历各行、内循环遍历各列。 边界条件在动态规划中用于初始化 表在搜索中用于剪枝。
状态转移顺序的核心是要保证在计算当前问题的解时所有它依赖的更小子问题的解都已经被正确地计算出来。
根据以上分析我们已经可以直接写出动态规划代码。然而子问题分解是一种从顶至底的思想因此按照 暴力搜索 → 记忆化搜索 → 动态规划 的顺序实现更加符合思维习惯。
1. 方法一暴力搜索
从状态 [ , ] 开始搜索不断分解为更小的状态 [ − 1, ] 和 [ , − 1 ] 递归函数包括以下要素。
递归参数状态 [ , ] 。返回值从 [ 0, 0 ] 到 [ , ] 的最小路径和 [ , ] 。终止条件当 0 且 0 时返回代价 [ 0, 0 ] 。剪枝当 0 时或 0 时索引越界此时返回代价 ∞ 代表不可行。
/* 最小路径和暴力搜索 */
int minPathSumDFS(int[][] grid, int i, int j) {// 若为左上角单元格则终止搜索if (i 0 j 0) {return grid[0][0];}// 若行列索引越界则返回 ∞ 代价if (i 0 || j 0) {return Integer.MAX_VALUE;}// 计算从左上角到 (i-1, j) 和 (i, j-1) 的最小路径代价int up minPathSumDFS(grid, i - 1, j);int left minPathSumDFS(grid, i, j - 1);// 返回从左上角到 (i, j) 的最小路径代价return Math.min(left, up) grid[i][j];
}下图给出了以 [ 2, 1 ] 为根节点的递归树其中包含一些重叠子问题其数量会随着网格 grid 的尺寸变大而急剧增多。 本质上看造成重叠子问题的原因为存在多条路径可以从左上角到达某一单元格。 每个状态都有向下和向右两种选择从左上角走到右下角总共需要 − 2 步所以最差时间复杂度为(2) 。 请注意这种计算方式未考虑临近网格边界的情况当到达网络边界时只剩下一种选择。因此实际的路径数量会少一些。
2. 方法二记忆化搜索
我们引入一个和网格 grid 相同尺寸的记忆列表 mem 用于记录各个子问题的解并将重叠子问题进行剪枝。
/* 最小路径和记忆化搜索 */
int minPathSumDFSMem(int[][] grid, int[][] mem, int i, int j) {// 若为左上角单元格则终止搜索if (i 0 j 0) {return grid[0][0];}// 若行列索引越界则返回 ∞ 代价if (i 0 || j 0) {return Integer.MAX_VALUE;}// 若已有记录则直接返回if (mem[i][j] ! -1) {return mem[i][j];}// 左边和上边单元格的最小路径代价int up minPathSumDFSMem(grid, mem, i - 1, j);int left minPathSumDFSMem(grid, mem, i, j - 1);// 记录并返回左上角到 (i, j) 的最小路径代价mem[i][j] Math.min(left, up) grid[i][j];return mem[i][j];
}如图所示在引入记忆化后所有子问题的解只需计算一次因此时间复杂度取决于状态总数即网格尺寸 () 。
3. 方法三动态规划
基于迭代实现动态规划解法:
/* 最小路径和动态规划 */
int minPathSumDP(int[][] grid) {int n grid.length, m grid[0].length;// 初始化 dp 表int[][] dp new int[n][m];dp[0][0] grid[0][0];// 状态转移首行for (int j 1; j m; j) {dp[0][j] dp[0][j - 1] grid[0][j];}// 状态转移首列for (int i 1; i n; i) {dp[i][0] dp[i - 1][0] grid[i][0];}// 状态转移其余行列for (int i 1; i n; i) {for (int j 1; j m; j) {dp[i][j] Math.min(dp[i][j - 1], dp[i - 1][j]) grid[i][j];}}return dp[n - 1][m - 1];
}下图展示了最小路径和的状态转移过程其遍历了整个网格因此时间复杂度为 () 。 数组 dp 大小为 × 因此空间复杂度为 () 。
4. 空间优化
由于每个格子只与其左边和上边的格子有关因此我们可以只用一个单行数组来实现 表。 请注意因为数组 dp 只能表示一行的状态所以我们无法提前初始化首列状态而是在遍历每行中更新它。
/* 最小路径和空间优化后的动态规划 */
int minPathSumDPComp(int[][] grid) {int n grid.length, m grid[0].length;// 初始化 dp 表int[] dp new int[m];// 状态转移首行dp[0] grid[0][0];for (int j 1; j m; j) {dp[j] dp[j - 1] grid[0][j];}// 状态转移其余行for (int i 1; i n; i) {// 状态转移首列dp[0] dp[0] grid[i][0];// 状态转移其余列for (int j 1; j m; j) {dp[j] Math.min(dp[j - 1], dp[j]) grid[i][j];}}return dp[m - 1];
}0‑1 背包问题
背包问题是一个非常好的动态规划入门题目是动态规划中最常见的问题形式。其具有很多变种例如 0‑1背包问题、完全背包问题、多重背包问题等。
在本节中我们先来求解最常见的 0‑1 背包问题。
问题 给定 个物品第 个物品的重量为 [ − 1]、价值为 [ − 1] 和一个容量为 的背包。每个物品只能选择一次问在不超过背包容量下能放入物品的最大价值。
观察下图由于物品编号 从 1 开始计数数组索引从 0 开始计数因此物品 对应重量 [ − 1 ] 和价值 [ − 1 ] 。 我们可以将 0‑1 背包问题看作是一个由 轮决策组成的过程每个物体都有不放入和放入两种决策因此该问题是满足决策树模型的。
该问题的目标是求解 在限定背包容量下的最大价值 因此较大概率是个动态规划问题。 第一步思考每轮的决策定义状态从而得到 表
对于每个物品来说不放入背包背包容量不变放入背包背包容量减小。由 此可得状态定义当前物品编号 和剩余背包容量 记为 [ , ] 。
状态 [ , ] 对应的子问题为前 个物品在剩余容量为 的背包中的最大价值记为 [ , ] 。待求解的是 [ , ] 因此需要一个尺寸为 ( 1) × ( 1) 的二维 表。
第二步找出最优子结构进而推导出状态转移方程 当我们做出物品 的决策后剩余的是前 − 1 个物品的决策可分为以下两种情况。
不放入物品 背包容量不变状态变化为 [ − 1, ] 。放入物品 背包容量减小 [ − 1 ] 价值增加 [ − 1 ] 状态变化为 [ − 1, − [ − 1 ] ] 。
上述分析向我们揭示了本题的最优子结构最大价值 [, ] 等于不放入物品 和放入物品 两种方案中的价值更大的那一个。由此可推出状态转移方程 需要注意的是若当前物品重量 [ − 1] 超出剩余背包容量 则只能选择不放入背包。 第三步确定边界条件和状态转移顺序 当无物品或无剩余背包容量时最大价值为 0 即首列 [ , 0 ] 和首行 [ 0, ] 都等于 0 。 当前状态 [ , ] 从上方的状态 [ − 1, ] 和左上方的状态 [ − 1, − [ − 1 ] ] 转移而来因此通过两层循环正序遍历整个 表即可。
根据以上分析我们接下来按顺序实现暴力搜索、记忆化搜索、动态规划解法。
1. 方法一暴力搜索
搜索代码包含以下要素
递归参数状态 [, ] 。返回值子问题的解 [, ] 。终止条件当物品编号越界 0 或背包剩余容量为 0 时终止递归并返回价值 0 。剪枝若当前物品重量超出背包剩余容量则只能不放入背包。
/* 0-1 背包暴力搜索 */
int knapsackDFS(int[] wgt, int[] val, int i, int c) {// 若已选完所有物品或背包无容量则返回价值 0if (i 0 || c 0) {return 0;}// 若超过背包容量则只能不放入背包if (wgt[i - 1] c) {return knapsackDFS(wgt, val, i - 1, c);}// 计算不放入和放入物品 i 的最大价值int no knapsackDFS(wgt, val, i - 1, c);int yes knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) val[i - 1];// 返回两种方案中价值更大的那一个return Math.max(no, yes);
}如图所示由于每个物品都会产生不选和选两条搜索分支因此时间复杂度为 (2) 。
观察递归树容易发现其中存在重叠子问题例如 [ 1, 10 ] 等。而当物品较多、背包容量较大尤其是相同重量的物品较多时重叠子问题的数量将会大幅增多。
2. 方法二记忆化搜索
为了保证重叠子问题只被计算一次我们借助记忆列表 mem 来记录子问题的解其中 mem [ i ] [ c ] 对应 [ , ]。 引入记忆化之后时间复杂度取决于子问题数量也就是 ( × ) 。
/* 0-1 背包记忆化搜索 */
int knapsackDFSMem(int[] wgt, int[] val, int[][] mem, int i, int c) {// 若已选完所有物品或背包无容量则返回价值 0if (i 0 || c 0) {return 0;}// 若已有记录则直接返回if (mem[i][c] ! -1) {return mem[i][c];}// 若超过背包容量则只能不放入背包if (wgt[i - 1] c) {return knapsackDFSMem(wgt, val, mem, i - 1, c);}// 计算不放入和放入物品 i 的最大价值int no knapsackDFSMem(wgt, val, mem, i - 1, c);int yes knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) val[i - 1];// 记录并返回两种方案中价值更大的那一个mem[i][c] Math.max(no, yes);return mem[i][c];
}下图展示了在记忆化递归中被剪掉的搜索分支。
3. 方法三动态规划
动态规划实质上就是在状态转移中填充 表的过程代码如下所示。
/* 0-1 背包动态规划 */
int knapsackDP(int[] wgt, int[] val, int cap) {int n wgt.length;// 初始化 dp 表int[][] dp new int[n 1][cap 1];// 状态转移for (int i 1; i n; i) {for (int c 1; c cap; c) {if (wgt[i - 1] c) {// 若超过背包容量则不选物品 idp[i][c] dp[i - 1][c];} else {// 不选和选物品 i 这两种方案的较大值dp[i][c] Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] val[i - 1]);}}}return dp[n][cap];
}如图所示时间复杂度和空间复杂度都由数组 dp 大小决定即 ( × ) 。 4. 空间优化
由于每个状态都只与其上一行的状态有关因此我们可以使用两个数组滚动前进将空间复杂度从 (2)将低至 () 。
进一步思考我们是否可以仅用一个数组实现空间优化呢 观察可知每个状态都是由正上方或左上方的格子转移过来的。假设只有一个数组当开始遍历第 行时该数组存储的仍然是第 − 1 行的状态。
如果采取正序遍历那么遍历到 [, ] 时左上方 [ − 1, 1] ~ [ − 1, − 1] 值可能已经被覆盖此时就无法得到正确的状态转移结果。如果采取倒序遍历则不会发生覆盖问题状态转移可以正确进行。
下图展示了在单个数组下从第 1 行转换至第 2 行的过程。请思考正序遍历和倒序遍历的区别。 在代码实现中我们仅需将数组 dp 的第一维 直接删除并且把内循环更改为倒序遍历即可。
/* 0-1 背包空间优化后的动态规划 */
int knapsackDPComp(int[] wgt, int[] val, int cap) {int n wgt.length;// 初始化 dp 表int[] dp new int[cap 1];// 状态转移for (int i 1; i n; i) {// 倒序遍历for (int c cap; c 1; c--) {if (wgt[i - 1] c) {// 不选和选物品 i 这两种方案的较大值dp[c] Math.max(dp[c], dp[c - wgt[i - 1]] val[i - 1]);}}}return dp[cap];
}完全背包问题
在本节中我们先求解另一个常见的背包问题完全背包 再了解它的一种特例零钱兑换。
完全背包
给定 个物品第 个物品的重量为 [ − 1 ]、价值为 [ − 1 ] 和一个容量为 的背包。每个物品可以重复选取问在不超过背包容量下能放入物品的最大价值。
1. 动态规划思路
完全背包和 0‑1 背包问题非常相似区别仅在于不限制物品的选择次数。
在 0‑1 背包中每个物品只有一个因此将物品 放入背包后只能从前 − 1 个物品中选择。在完全背包中每个物品有无数个因此将物品 放入背包后仍可以从前 个物品中选择。
在完全背包的规定下状态 [, ] 的变化分为两种情况:
不放入物品 与 0‑1 背包相同转移至 [ − 1, ] 。放入物品 与 0‑1 背包不同转移至 [, − [ − 1]] 。
从而状态转移方程变为
2. 代码实现
对比两道题目的代码状态转移中有一处从 − 1 变为 其余完全一致。
/* 完全背包动态规划 */
int unboundedKnapsackDP(int[] wgt, int[] val, int cap) {int n wgt.length;// 初始化 dp 表int[][] dp new int[n 1][cap 1];// 状态转移for (int i 1; i n; i) {for (int c 1; c cap; c) {if (wgt[i - 1] c) {// 若超过背包容量则不选物品 idp[i][c] dp[i - 1][c];} else {// 不选和选物品 i 这两种方案的较大值dp[i][c] Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] val[i - 1]);}}}return dp[n][cap];
}3. 空间优化
由于当前状态是从左边和上边的状态转移而来因此空间优化后应该对 表中的每一行采取正序遍历。 这个遍历顺序与 0‑1 背包正好相反。请借助下图来理解两者的区别。 代码实现比较简单仅需将数组 dp 的第一维删除。
/* 完全背包空间优化后的动态规划 */
int unboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {int n wgt.length;// 初始化 dp 表int[] dp new int[cap 1];// 状态转移for (int i 1; i n; i) {for (int c 1; c cap; c) {if (wgt[i - 1] c) {// 若超过背包容量则不选物品 idp[c] dp[c];} else {// 不选和选物品 i 这两种方案的较大值dp[c] Math.max(dp[c], dp[c - wgt[i - 1]] val[i - 1]);}}}return dp[cap];
}零钱兑换问题
背包问题是一大类动态规划问题的代表其拥有很多的变种例如零钱兑换问题。 给定 种硬币第 种硬币的面值为 [ − 1 ] 目标金额为 每种硬币可以重复选取问能够凑出目标金额的最少硬币个数。如果无法凑出目标金额则返回 −1 。 1. 动态规划思路
零钱兑换可以看作是完全背包的一种特殊情况两者具有以下联系与不同点。
两道题可以相互转换 物品 对应于 硬币 、 物品重量 对应于 硬币面值 、 背包容量 对应于 目标金额 。优化目标相反背包问题是要最大化物品价值零钱兑换问题是要最小化硬币数量。背包问题是求 不超过 背包容量下的解零钱兑换是求 恰好 凑到目标金额的解。 第一步思考每轮的决策定义状态从而得到 表
状态 [ , ] 对应的子问题为前 种硬币能够凑出金额 的最少硬币个数记为 [ , ]。二维 表的尺寸为 ( 1) × ( 1) 。
第二步找出最优子结构进而推导出状态转移方程 本题与完全背包的状态转移方程存在以下两个差异。
本题要求最小值因此需将运算符 max() 更改为 min() 。优化主体是硬币数量而非商品价值因此在选中硬币时执行 1 即可。 第三步确定边界条件和状态转移顺序 当目标金额为 0 时凑出它的最少硬币个数为 0 即首列所有 [ , 0 ] 都等于 0 。
当无硬币时无法凑出任意 0 的目标金额即是无效解。为使状态转移方程中的 min() 函数能够识别并过滤无效解我们考虑使用 ∞ \infty ∞ 来表示它们即令首行所有 [ 0, ]都等于 ∞ \infty ∞
2. 代码实现
大多数编程语言并未提供 ∞ \infty ∞ 变量只能使用整型 int 的最大值来代替。 而这又会导致大数越界状态转移方程中的 1 操作可能发生溢出。 为此我们采用数字 1 来表示无效解因为凑出 的硬币个数最多为 个。 最后返回前判断 [, ] 是否等于 1 若是则返回 −1 代表无法凑出目标金额。
/* 零钱兑换动态规划 */
int coinChangeDP(int[] coins, int amt) {int n coins.length;int MAX amt 1;// 初始化 dp 表int[][] dp new int[n 1][amt 1];// 状态转移首行首列for (int a 1; a amt; a) {dp[0][a] MAX;}// 状态转移其余行列for (int i 1; i n; i) {for (int a 1; a amt; a) {if (coins[i - 1] a) {// 若超过背包容量则不选硬币 idp[i][a] dp[i - 1][a];} else {// 不选和选硬币 i 这两种方案的较小值dp[i][a] Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] 1);}}}return dp[n][amt] ! MAX ? dp[n][amt] : -1;
}下图展示了零钱兑换的动态规划过程和完全背包非常相似。 3. 空间优化
零钱兑换的空间优化的处理方式和完全背包一致。
/* 零钱兑换空间优化后的动态规划 */
int coinChangeDPComp(int[] coins, int amt) {int n coins.length;int MAX amt 1;// 初始化 dp 表int[] dp new int[amt 1];Arrays.fill(dp, MAX);dp[0] 0;// 状态转移for (int i 1; i n; i) {for (int a 1; a amt; a) {if (coins[i - 1] a) {// 若超过背包容量则不选硬币 idp[a] dp[a];} else {// 不选和选硬币 i 这两种方案的较小值dp[a] Math.min(dp[a], dp[a - coins[i - 1]] 1);}}}return dp[amt] ! MAX ? dp[amt] : -1;
}零钱兑换问题 II
给定 种硬币第 种硬币的面值为 [ − 1 ] 目标金额为 每种硬币可以重复选取问在凑出目标金额的硬币组合数量。
1. 动态规划思路
相比于上一题本题目标是组合数量因此子问题变为前 种硬币能够凑出金额 的组合数量。 而 表仍然是尺寸为 ( 1) × ( 1) 的二维矩阵。
当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和。 状态转移方程为 当目标金额为 0 时无须选择任何硬币即可凑出目标金额因此应将首列所有 [ , 0 ] 都初始化为 1 。当无硬币时无法凑出任何 0 的目标金额因此首行所有 [ 0, ] 都等于 0 。
2. 代码实现
/* 零钱兑换 II动态规划 */
int coinChangeIIDP(int[] coins, int amt) {int n coins.length;// 初始化 dp 表int[][] dp new int[n 1][amt 1];// 初始化首列for (int i 0; i n; i) {dp[i][0] 1;}// 状态转移for (int i 1; i n; i) {for (int a 1; a amt; a) {if (coins[i - 1] a) {// 若超过背包容量则不选硬币 idp[i][a] dp[i - 1][a];} else {// 不选和选硬币 i 这两种方案之和dp[i][a] dp[i - 1][a] dp[i][a - coins[i - 1]];}}}return dp[n][amt];
}3. 空间优化
空间优化处理方式相同删除硬币维度即可
/* 零钱兑换 II空间优化后的动态规划 */
int coinChangeIIDPComp(int[] coins, int amt) {int n coins.length;// 初始化 dp 表int[] dp new int[amt 1];dp[0] 1;// 状态转移for (int i 1; i n; i) {for (int a 1; a amt; a) {if (coins[i - 1] a) {// 若超过背包容量则不选硬币 idp[a] dp[a];} else {// 不选和选硬币 i 这两种方案之和dp[a] dp[a] dp[a - coins[i - 1]];}}}return dp[amt];
}编辑距离问题
编辑距离也被称为 Levenshtein 距离指两个字符串之间互相转换的最小修改次数通常用于在信息检索和自然语言处理中度量两个序列的相似度。
问题 输入两个字符串 和 返回将 转换为 所需的最少编辑步数。 你可以在一个字符串中进行三种编辑操作插入一个字符、删除一个字符、替换字符为任意一个字符。
如图所示将 kitten 转换为 sitting 需要编辑 3 步包括 2 次替换操作与 1 次添加操作将 hello 转换为 algo 需要 3 步包括 2 次替换操作和 1 次删除操作。 编辑距离问题可以很自然地用决策树模型来解释。字符串对应树节点一轮决策一次编辑操作对应树的一条边。
如图所示在不限制操作的情况下每个节点都可以派生出许多条边每条边对应一种操作这意味着从 hello 转换到 algo 有许多种可能的路径。 从决策树的角度看本题的目标是求解节点 hello 和节点 algo 之间的最短路径。 1. 动态规划思路
第一步思考每轮的决策定义状态从而得到 表 每一轮的决策是对字符串 进行一次编辑操作。 我们希望在编辑操作的过程中问题的规模逐渐缩小这样才能构建子问题。 设字符串 和 的长度分别为 和 我们先考虑两字符串尾部的字符 [ − 1 ] 和 [ − 1 ] 。
若 [ − 1 ] 和 [ − 1 ] 相同我们可以跳过它们直接考虑 [ − 2 ] 和 [ − 2 ] 。若 [ − 1 ] 和 [ − 1 ] 不同我们需要对 进行一次编辑插入、删除、替换使得两字符串尾部的字符相同从而可以跳过它们考虑规模更小的问题。
也就是说我们在字符串 中进行的每一轮决策编辑操作都会使得 和 中剩余的待匹配字符发生变化。 因此状态为当前在 和 中考虑的第 和 个字符记为 [ , ] 。 状态 [ , ] 对应的子问题将 的前 个字符更改为 的前 个字符所需的最少编辑步数。 至此得到一个尺寸为 ( 1) × ( 1) 的二维 表。
第二步找出最优子结构进而推导出状态转移方程 考虑子问题 [ , ] 其对应的两个字符串的尾部字符为 [ − 1 ] 和 [ − 1 ] 可根据不同编辑操作分为下图所示的三种情况。
在 [ − 1] 之后添加 [ − 1 ] 则剩余子问题 [ , − 1 ] 。删除 [ − 1 ] 则剩余子问题 [ − 1, ] 。将 [ − 1 ] 替换为 [ − 1 ] 则剩余子问题 [ − 1, − 1 ] 。 根据以上分析可得最优子结构 [ , ] 的最少编辑步数等于 [ , − 1 ]、 [ − 1, ]、 [ − 1, − 1 ]三者中的最少编辑步数再加上本次的编辑步数 1 。对应的状态转移方程为 请注意当 [ − 1 ] 和 [ − 1 ] 相同时无须编辑当前字符这种情况下的状态转移方程为 第三步确定边界条件和状态转移顺序 当两字符串都为空时编辑步数为 0 即 [0, 0] 0 。当 为空但 不为空时最少编辑步数等于 的长度即首行 [0, ] 。当 不为空但 为空时等于 的长度即首列 [, 0] 。
观察状态转移方程解 [, ] 依赖左方、上方、左上方的解因此通过两层循环正序遍历整个 表即可。
2. 代码实现
/* 编辑距离动态规划 */
int editDistanceDP(String s, String t) {int n s.length(), m t.length();int[][] dp new int[n 1][m 1];// 状态转移首行首列for (int i 1; i n; i) {dp[i][0] i;}for (int j 1; j m; j) {dp[0][j] j;}// 状态转移其余行列for (int i 1; i n; i) {for (int j 1; j m; j) {if (s.charAt(i - 1) t.charAt(j - 1)) {// 若两字符相等则直接跳过此两字符dp[i][j] dp[i - 1][j - 1];} else {// 最少编辑步数 插入、删除、替换这三种操作的最少编辑步数 1dp[i][j] Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) 1;}}}return dp[n][m];
}如图所示编辑距离问题的状态转移过程与背包问题非常类似都可以看作是填写一个二维网格的过程。
3. 空间优化
由于 [ , ] 是由上方 [ − 1, ]、左方 [ , − 1 ]、左上方状态 [ − 1, − 1 ] 转移而来 而正序遍历会丢失左上方 [ − 1, − 1 ] 倒序遍历无法提前构建 [ , − 1 ] 因此两种遍历顺序都不可取。 为此我们可以使用一个变量 leftup 来暂存左上方的解 [ − 1, − 1 ] 从而只需考虑左方和上方的解。 此时的情况与完全背包问题相同可使用正序遍历。
/* 编辑距离空间优化后的动态规划 */
int editDistanceDPComp(String s, String t) {int n s.length(), m t.length();int[] dp new int[m 1];// 状态转移首行for (int j 1; j m; j) {dp[j] j;}// 状态转移其余行for (int i 1; i n; i) {// 状态转移首列int leftup dp[0]; // 暂存 dp[i-1, j-1]dp[0] i;// 状态转移其余列for (int j 1; j m; j) {int temp dp[j];if (s.charAt(i - 1) t.charAt(j - 1)) {// 若两字符相等则直接跳过此两字符dp[j] leftup;} else {// 最少编辑步数 插入、删除、替换这三种操作的最少编辑步数 1dp[j] Math.min(Math.min(dp[j - 1], dp[j]), leftup) 1;}leftup temp; // 更新为下一轮的 dp[i-1, j-1]}}return dp[m];
}总结
动态规划对问题进行分解并通过存储子问题的解来规避重复计算实现高效的计算效率。不考虑时间的前提下所有动态规划问题都可以用回溯暴力搜索进行求解但递归树中存在大量的重叠子问题效率极低。通过引入记忆化列表可以存储所有计算过的子问题的解从而保证重叠子问题只被计算一次。记忆化递归是一种从顶至底的递归式解法而与之对应的动态规划是一种从底至顶的递推式解法其如同“填写表格”一样。由于当前状态仅依赖于某些局部状态因此我们可以消除 表的一个维度从而降低空间复杂度。子问题分解是一种通用的算法思路在分治、动态规划、回溯中具有不同的性质。动态规划问题的三大特性重叠子问题、最优子结构、无后效性。如果原问题的最优解可以从子问题的最优解构建得来则它就具有最优子结构。无后效性指对于一个状态其未来发展只与该状态有关与其所经历的过去的所有状态无关。许多组合优化问题都不具有无后效性无法使用动态规划快速求解。
背包问题
背包问题是最典型的动态规划题目具有 0‑1 背包、完全背包、多重背包等变种问题。0‑1 背包的状态定义为前 个物品在剩余容量为 的背包中的最大价值。根据不放入背包和放入背包两种决策可得到最优子结构并构建出状态转移方程。在空间优化中由于每个状态依赖正上方和左上方的状态因此需要倒序遍历列表避免左上方状态被覆盖。完全背包的每种物品的选取数量无限制因此选择放入物品的状态转移与 0‑1 背包不同。由于状态依赖于正上方和正左方的状态因此在空间优化中应当正序遍历。零钱兑换问题是完全背包的一个变种。它从求“最大”价值变为求“最小”硬币数量因此状态转移方程中的 max() 应改为 min() 。从求“不超过”背包容量到求“恰好”凑出目标金额因此使用 1来表示“无法凑出目标金额”的无效解。零钱兑换 II 问题从求“最少硬币数量”改为求“硬币组合数量”状态转移方程相应地从 min() 改为求和运算符。
编辑距离问题
编辑距离Levenshtein 距离用于衡量两个字符串之间的相似度其定义为从一个字符串到另一个字符串的最小编辑步数编辑操作包括添加、删除、替换。编辑距离问题的状态定义为将 的前 个字符更改为 的前 个字符所需的最少编辑步数。当[] ≠ [] 时具有三种决策添加、删除、替换它们都有相应的剩余子问题。据此便可以找出最优子结构与构建状态转移方程。而当 [] [] 时无须编辑当前字符。在编辑距离中状态依赖于其正上方、正左方、左上方的状态因此空间优化后正序或倒序遍历都无法正确地进行状态转移。为此我们利用一个变量暂存左上方状态从而转化到与完全背包等价的情况可以在空间优化后进行正序遍历。
