动态规划笔记

1. 概念

动态规划（Dynamic Programming，简称DP）是一种将复杂问题分解为更小的子问题，利用子问题的最优解构建原问题最优解的算法设计方法。它常用于求解最优化问题，具有高效性和广泛的应用。

1.1 问题特性

要判断一个问题是否适合用动态规划来解决，通常需要满足以下特性：

1. 最优子结构（Optimal Substructure）：

   • 定义：一个问题的最优解包含其子问题的最优解。
   • 举例：在最短路径问题中，从节点 A 到节点 C 的最短路径可以拆分为从 A 到 B 的最短路径加上从 B 到 C 的最短路径。

2. 无后效性（No Aftereffect）：

   • 定义：当前状态的决策不会影响未来状态的决策，即状态转移只依赖于当前状态，而与之前的状态或决策路径无关。
   • 举例：在背包问题中，放入某个物品后，背包的剩余容量只取决于当前已经放入的物品总重量，与放入顺序无关。

3. 重叠子问题（Overlapping Subproblems）：

   • 定义：不同的决策序列会涉及到相同的子问题，这些子问题会被多次计算。
   • 举例：计算斐波那契数列时，F(n) = F(n-1) + F(n-2)，F(n-1) 和 F(n-2) 会被多次重复计算。
     

1.2 问题判断

在面对一个新的问题时，如何判断它是否适合用动态规划来解决？以下是一些判断标准和模型：

动态规划问题的特点：

1. 明确的状态和决策：

   • 问题可以通过一系列决策来解决，每个决策会改变问题的状态。
   • 状态：描述当前所处的位置或条件。
   • 决策：在当前状态下可选择的行动。

2. 递推关系（状态转移方程）：

   • 存在明确的状态转移方程，描述从一个状态如何转移到下一个状态。

动态规划问题的模型：

动态规划通常使用 “决策树模型” 或 “状态转移图” 来描述问题：

• 决策树模型：

  • 节点：代表问题的不同状态。
  • 边：代表从一个状态到另一个状态的可能决策。
  • 路径：代表一系列决策序列。

• 状态转移图：

  • 用图的形式表示状态之间的转移关系，帮助理解状态转移方程。

判断标准：“加分项”和“减分项”

加分项：

• 优化目标：问题要求找到最优值，如最大值、最小值、最长、最短等。
• 状态可表示性：问题的状态可以用一组变量（标量或多维数组）来表示。
• 状态转移的确定性：从当前状态出发，决策后的新状态是确定的。

减分项：

• 求解所有方案：问题需要列举所有可能的解，而不是一个最优解。
• 明显的组合或排列特征：问题更适合用穷举、递归或回溯来解决。

总结：

如果一个问题具有最优子结构、无后效性和重叠子问题，且优化目标明确，状态易于表示，那么它很可能适合用动态规划来解决。

1.3 如何解题

解决动态规划问题的步骤通常包括：

1. 第一步：定义状态和决策，构建 DP 表
   

   • 思考每轮的决策：在问题中，每一步有哪些可能的选择？
   • 定义状态（State）：状态通常由多个变量组成，用于描述当前所处的情况。
     • 例子：在背包问题中，状态可以用 dp[i][w] 表示前 i 个物品在容量为 w 的背包中能取得的最大价值。
   • 构建 DP 表：根据状态，建立一维或多维的 DP 数组，用于存储子问题的解。

2. 第二步：推导状态转移方程

   • 找出最优子结构：理解如何利用子问题的解来构建当前问题的解。
   • 推导状态转移方程：描述状态之间如何转移的关系。
     • 例子：在背包问题中，状态转移方程为：

       dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
       

       表示第 i 个物品放入或不放入背包的两种情况取较大值。

3. 第三步：确定边界条件和状态转移顺序

   • 边界条件：
     • 初始化：设置初始状态的值，确保 DP 表的第一个元素有正确的值。
       • 例子：dp[0][w] = 0，表示当没有物品时，无论背包容量是多少，价值都为 0。
   • 状态转移顺序：
     • 确定计算顺序：根据状态转移方程，决定是从小到大还是从大到小遍历。
       • 例子：在背包问题中，通常从小到大遍历物品，从大到小遍历容量，以避免重复计算和覆盖。

4. 第四步：实现与优化

   • 代码实现：按照前面的步骤，编写代码，实现动态规划算法。

   • 空间优化：

     • 滚动数组：如果当前状态只依赖于前一个状态，可以使用滚动数组减少空间复杂度。
     • 状态压缩：对于一些特定问题，可以将多维 DP 压缩为一维。

   • 时间优化：

     • 剪枝：在计算过程中，跳过不必要的计算，减少时间消耗。
     • 记忆化搜索：结合递归和缓存，避免重复计算。

2. 常见动态规划问题类型

动态规划在计算机算法中有广泛的应用，以下是一些经典的动态规划问题类型：

2.1 背包问题

• 01 背包问题：给定一组物品，每个物品有重量和价值，在限定的总重量内，如何选择物品使得总价值最大。
• 完全背包问题：物品数量无限，每种物品可以选择任意多个。
• 多重背包问题：物品数量有限，每种物品有一个最大可选数量。

2.2 最长子序列问题

• 最长公共子序列（LCS）：找到两个序列的最长公共子序列。
• 最长递增子序列（LIS）：找到序列中最长的递增子序列。

2.3 编辑距离问题

• 编辑距离（Levenshtein Distance）：计算将一个字符串转换为另一个字符串所需的最小编辑操作次数（插入、删除、替换）。

2.4 数塔问题

• 三角形最小路径和：在一个数字三角形中，从顶部到底部走一条路径，使路径上的数字和最小。

2.5 其他经典问题

• 硬币找零问题：给定面值的硬币，如何凑出指定金额的最少硬币数。
• 区间调度问题：在给定的时间区间内，选择尽可能多的互不重叠的活动。

3. 动态规划的优化技巧

3.1 空间复杂度优化

• 滚动数组：当状态转移只依赖于前一状态时，可以用一维数组代替二维数组。
  • 例子：将 dp[i][w] 压缩为 dp[w]。

3.2 状态压缩

• 位运算压缩：对于状态数量为 2 的幂次的问题，可以使用位运算压缩状态。
  • 例子：在旅行商问题（TSP）中，用位掩码表示城市的访问状态。

3.3 记忆化搜索

• 递归 + 记忆化：使用递归求解，同时将计算结果缓存，避免重复计算。
  • 适用场景：状态空间大，但实际被访问的状态较少。

3.4 DP + 二分

• 结合二分查找：在一些需要查找的位置上，使用二分查找优化。
  • 例子：最长递增子序列的时间复杂度可以从 O(n^2) 优化到 O(n log n)。

4. 实战案例

案例1：斐波那契数列

• 问题描述：求第 N 个斐波那契数。
• 状态定义：dp[n] 表示第 N 个斐波那契数。
• 状态转移方程：dp[n] = dp[n-1] + dp[n-2]。
• 边界条件：dp[0] = 0, dp[1] = 1。

案例2：01 背包问题

• 问题描述：选择物品放入背包，使得总价值最大，且总重量不超过背包容量。
• 状态定义：dp[i][w] 表示前 i 个物品在容量为 w 的情况下的最大价值。
• 状态转移方程：

  dp[i][w] = dp[i-1][w], 如果不选第 i 个物品；
  dp[i][w] = dp[i-1][w - weight[i]] + value[i], 如果选第 i 个物品。
  

• 边界条件：dp[0][w] = 0。

案例3：最长公共子序列（LCS）

• 问题描述：求两个字符串的最长公共子序列长度。
• 状态定义：dp[i][j] 表示字符串 A 的前 i 个字符和字符串 B 的前 j 个字符的 LCS 长度。
• 状态转移方程：
  • 如果 A[i] == B[j]，则 dp[i][j] = dp[i-1][j-1] + 1；
  • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
• 边界条件：dp[0][j] = dp[i][0] = 0。

参考

1. hello算法

原文地址：https://blog.csdn.net/weixin_51147313/article/details/143814231

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！