C++动态规划实现与问题解析

动态规划，说白了，就是把一个复杂问题拆解成一堆更小的、相互关联的子问题，然后解决这些子问题，最后把它们的答案组合起来，得到原始问题的答案。关键在于，子问题之间不是独立的，它们会互相重叠，动态规划就是用来避免重复计算这些重叠的子问题。

C++中实现动态规划，主要就是两招：记忆化搜索和递推。

解决方案

具体来说，我们通常会创建一个表格（比如二维数组vector> dp），用来存储子问题的解。这个表格的维度取决于问题的性质。然后，根据问题的状态转移方程，来填充这个表格。

• 记忆化搜索：本质上是递归，但加了一个缓存，避免重复计算。 比如，计算dp[i][j]时，先检查它是否已经被计算过。如果dp[i][j]已经有值了，直接返回；否则，根据状态转移方程计算dp[i][j]，并存入表格。

  #include 
  #include 
  
  using namespace std;
  
  int solve(int i, int j, vector>& dp) {
      if (i == 0 || j == 0) {
          return 0; // 边界条件
      }
  
      if (dp[i][j] != -1) {
          return dp[i][j]; // 已经计算过，直接返回
      }
  
      // 状态转移方程 (这里只是一个例子，具体问题具体分析)
      dp[i][j] = solve(i - 1, j, dp) + solve(i, j - 1, dp) + 1;
      return dp[i][j];
  }
  
  int main() {
      int n = 5, m = 6;
      vector> dp(n + 1, vector(m + 1, -1)); // 初始化为-1，表示未计算
      cout << solve(n, m, dp) << endl;
      return 0;
  }

• 递推：从最小的子问题开始，逐步计算更大的子问题，直到得到原始问题的解。 关键是确定计算顺序，保证在计算dp[i][j]时，它所依赖的子问题（比如dp[i-1][j]和dp[i][j-1]）已经被计算过了。

  #include 
  #include 
  
  using namespace std;
  
  int main() {
      int n = 5, m = 6;
      vector> dp(n + 1, vector(m + 1, 0)); // 初始化为0
  
      // 递推计算
      for (int i = 1; i <= n; ++i) {
          for (int j = 1; j <= m; ++j) {
              // 状态转移方程 (这里只是一个例子，具体问题具体分析)
              dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + 1;
          }
      }
  
      cout << dp[n][m] << endl;
      return 0;
  }

动态规划的难点在于：

1. 确定状态：状态就是子问题，需要仔细分析问题，找到能够表示子问题的变量。
2. 状态转移方程：状态转移方程描述了子问题之间的关系，是动态规划的核心。
3. 边界条件：边界条件是最小的子问题，可以直接求解。
4. 计算顺序：对于递推，需要确定合适的计算顺序，保证子问题在被使用之前已经计算出来。

如何选择记忆化搜索还是递推？

这其实没有绝对的答案，取决于个人偏好和问题的特点。

• 记忆化搜索：代码更简洁，更容易理解，特别是对于状态比较复杂的问题。 缺点是可能会有递归调用的开销，在某些情况下可能会栈溢出（可以通过手动扩展栈空间来解决）。
• 递推：效率更高，没有递归调用的开销。缺点是代码可能更复杂，需要仔细考虑计算顺序。

一般来说，如果问题比较复杂，状态比较多，我会倾向于使用记忆化搜索。如果问题比较简单，状态比较少，我会倾向于使用递推。

动态规划和贪心算法有什么区别？

动态规划和贪心算法都是用来解决优化问题的。但它们之间有很大的区别。

• 动态规划：考虑所有可能的解，选择最优的解。它通过将问题分解为子问题，并保存子问题的解，避免重复计算，从而提高效率。 动态规划通常适用于具有最优子结构和重叠子问题的问题。
• 贪心算法：每一步都选择当前看起来最好的解，希望最终得到全局最优解。贪心算法不保证得到最优解，但通常可以得到一个近似最优解。 贪心算法通常适用于具有贪心选择性质的问题。

举个例子，假设我们要找从A到B的最短路径。

• 动态规划：会考虑所有可能的路径，并选择最短的路径。
• 贪心算法：每一步都选择离B最近的节点，希望最终得到最短路径。但如果中间某个节点选择错误，可能会导致最终的路径不是最短的。

动态规划有哪些常见的应用场景？

动态规划应用非常广泛，比如：

• 背包问题：给定一组物品，每个物品有重量和价值，在不超过背包容量的前提下，选择哪些物品可以使得总价值最大。
• 最长公共子序列（LCS）：给定两个字符串，找到它们的最长公共子序列。
• 最长递增子序列（LIS）：给定一个序列，找到它的最长递增子序列。
• 编辑距离：给定两个字符串，计算将一个字符串转换成另一个字符串所需要的最少操作次数（插入、删除、替换）。
• 斐波那契数列：虽然可以直接递归或者循环计算，但用动态规划可以避免重复计算。
• 路径规划：在图或者网格中寻找最短路径或者最优路径。

总而言之，动态规划是一种强大的算法，可以用来解决很多优化问题。理解动态规划的思想，并掌握常见的动态规划问题的解法，对于提高编程能力非常有帮助。