数据结构-动态规划策略

动态规划

• 1.理解动态规划思想

  • 基本概念
    • 重叠子问题:原问题可以分解为若干个子问题，且这些子问题之间存在重复部分。也就是说，为了解决一个子问题，我们需要多次求解相同的子子问题。例如，在计算斐波那契数列时，计算第n项需要知道第n-1项和第n-2项，而计算第n-1项又需要知道第n-2项和第n-3项，如此反复，子问题被反复计算。
    • 最优子结构:原问题的最优解可以通过其子问题的最优解构造出来。这意味着，要找到整个问题的最优解，必须先确定子问题的最优解。例如，在求解最短路径问题时，从起点到终点的最短路径必然包含从起点到某个中间节点的最短路径。
  • 核心思想
    • 主要用于解决具有重叠子问题和最优子结构性质的问题。动态规划的核心思想是将原问题分解为相互重叠的子问题，并通过自底向上或自顶向下的方式逐步求解子问题，存储并利用已计算过的子问题结果（称为“状态”或“阶段”），避免重复计算，从而高效地求得原问题的最优解。

• 2.算法实现过程(状态与状态转移方程)

  • 状态的定义:明确问题中的状态变量及其取值范围。状态通常代表了问题在某一阶段或某一时刻的具体情况。
  • 状态转移方程:建立状态之间的递推关系，即如何从一个或多个较小规模的子问题状态计算出当前状态的值。这是动态规划的核心步骤，它确保了问题的求解能够以自底向上或自顶向下的方式进行。
  • 边界条件:确定递归过程的终止条件或初始状态值。这通常是问题规模最小或没有子问题时的状态值。例如，在斐波那契数列中，边界条件为 F(0) = 0 和 F(1) = 1。

• 3.动态规划实现方式

  • 记忆化搜索(自顶向下)
    1. 编写递归函数，遵循“先调用后计算”的原则，同时在函数内部添加缓存（如哈希表或数组），存储已计算过的子问题结果。
    2. 在每次递归调用时，首先检查缓存中是否存在对应子问题的解，若存在则直接返回；若不存在，则计算该子问题的解并将其存入缓存，再返回结果。
  • 迭代法(自底向上)
    • 使用循环结构遍历状态空间，按照问题规模从小到大的顺序，依次计算所有子问题的解。
    • 根据状态转移方程，利用已计算好的较小规模子问题的解来更新当前状态的值。
    • 将每个子问题的解保存在一个表格（如二维数组）中，便于后续访问。

• 4.动态规划的适用条件

  • 最优子结构
    • 问题的最优解包含其子问题的最优解。换句话说，要找到原问题的最优解，必须先确定其子问题的最优解。这意味着，问题的最优解可以通过组合子问题的最优解来构建，而无需考虑非最优的子问题解。
  • 重叠子问题
    • 在解决问题的过程中，相同的子问题会被多次遇到和求解。如果不采取措施避免重复计算，这种重复会导致不必要的计算开销，降低算法效率。
    • 动态规划通过保存已经计算过的子问题结果，避免了对同一子问题的重复求解，从而提高了效率。例如，在计算斐波那契数列时，计算第n项需要知道第n-1项和第n-2项，而计算第n-1项又需要知道第n-2项和第n-3项，如果没有缓存先前的结果，就会出现大量的重复计算。
  • 无后效性
    • 当前状态的决策只依赖于当前状态本身及之前的状态，而不依赖于未来状态或之后的决策。也就是说，一旦确定了一个状态的值，未来的决策不会影响这个状态值的变化。
    • 无后效性保证了状态转移过程的确定性，使得我们可以放心地根据当前状态计算下一个状态，而不需要担心未来决策会反过来影响当前状态的计算。

• 5.动态规划的时间复杂度分析

  • 状态空间大小
    • 状态数（n）：问题中可能存在的不同状态的数量。这通常由状态变量的取值范围决定。例如，在经典的0/1背包问题中，状态变量可能包括物品编号和背包剩余容量，状态数随物品数量和背包容量的不同而变化。
    • 状态维度（d）：问题中的状态变量个数。单变量问题通常对应一维状态空间，多变量问题则对应多维状态空间。状态维度会影响状态转移所需的计算次数。
  • 状态转移次数
    • 状态转移方程:分析状态转移方程以确定计算一个状态值所需的状态转移次数。这通常涉及到对状态空间中相邻状态（或相关状态）的访问次数。
    • 循环结构:如果使用迭代法（自底向上）实现，可以通过分析循环结构来确定状态转移次数。例如，双层循环通常对应状态转移次数为 O(n^2)，三层循环则可能对应 O(n^3)。
  • 状态转移复杂度
    • 单次转移操作:计算一个状态值所需的基本操作次数。
    • 总转移复杂度:将单次转移操作的复杂度乘以状态转移次数，得到总的转移复杂度
  • 边界条件处理
    • 初始化时间：处理边界条件所需的时间，通常为常数时间或与状态空间大小成线性关系。
    • 结果提取时间：从最终状态或状态表中提取最终答案所需的时间，同样通常为较低阶复杂度。
  • 总体时间复杂度
    • 动态规划算法的总体时间复杂度通常由上述各部分复杂度的最高阶项决定。

• 6.典型动态规划问题

  • 最长上升子序列
    • 问题描述:给定一个整数序列，找到其中最长的严格递增子序列（子序列中的元素严格递增，且不一定是连续的）的长度。
    • 动态规划思想
      • 状态定义:设 dp[i] 表示以原序列中第 i 个元素结尾的最长上升子序列的长度。
      • 状态转移:对于每个位置 i，考虑其前面所有较小的元素（A[j]，j < i），若存在 A[j] < A[i]，则以 A[i] 结尾的最长上升子序列长度至少为 dp[j] + 1。取所有这样的 dp[j] + 1 中的最大值作为 dp[i] 的值。
      • 动态规划方程:dp[i] = max(dp[j] + 1)，其中 j 满足 0 <= j < i 且 A[j] < A[i]。
  • 0-1背包问题
    • 问题描述:给定一组物品，每种物品有一个重量 w_i 和一个价值 v_i，以及一个背包的容量 W。要求在不超过背包容量的前提下，选择物品放入背包，使得背包中物品的总价值最大。
    • 动态规划思想
      • 状态定义:设 dp[i][w][i][w]表示考虑前 i 件物品，背包容量为 w 时可以获得的最大价值。
      • 状态转移:对于每个物品 i 和背包容量 w，有两种选择：① 不放入物品 i，此时背包价值为 dp[i-1][w]；② 放入物品 i，若 w >= w_i，则背包价值为 dp[i-1][w-w_i] + v_i。取两者中价值较大者作为 dp[i][w] 的值。
      • 动态规划方程:dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i)，其中 w >= w_i；否则 dp[i][w] = dp[i-1][w]。
  • 最长公共子序列
    • 问题描述:给定两个字符串 str1 和 str2，找到它们的最长公共子序列（子序列中的字符按原顺序排列，且不一定连续）的长度
    • 动态规划思想
      • 状态定义:设 dp[i][j] 表示字符串 str1 前 i 个字符和字符串 str2 前 j 个字符的最长公共子序列的长度。
      • 状态转移:对于每对字符位置 (i, j)，若 str1[i-1] == str2[j-1]，说明当前i,j字符相同可以加入公共子序列，长度增加1，即 dp[i][j] = dp[i-1][j-1] + 1；否则，选择在 str1 或 str2 中保留更长的子序列，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
      • 动态规划方程:若 str1[i-1] == str2[j-1]），dp[i][j] = dp[i-1][j-1] + 1,否则 dp[i][j] = max(dp[i-\1][j], dp[i][j-1])。
  • 最大子数组之和
    • 问题描述:给定一个整数数组，找到其中具有最大和的连续子数组。
    • 动态规划思想
      • 状态定义:设 dp[i] 表示以原数组中第 i 个元素结尾的连续子数组的最大和。
      • 状态转移:对于每个位置 i，计算以 A[i] 结尾的子数组和，有两种情况：① 包含前一个元素 A[i-1]，则子数组和为 dp[i-1] + A[i]；② 只包含当前元素 A[i]，子数组和为 A[i]。取两者中和较大的作为 dp[i] 的值。
      • 动态规划方程:dp[i] = max(dp[i-1] + A[i], A[i]).其中 i > 0；dp[0] = A[0]（初始化）。