【C语言练习】052. 理解动态规划的基本概念_c语言 动态规划

052. 理解动态规划的基本概念

• 052. 理解动态规划的基本概念
• • 1. 动态规划的基本概念
  • • 1.1 最优子结构
    • 1.2 重叠子问题
    • 1.3 状态和状态转移方程
    • 重叠子问题
    • • 代码示例：斐波那契数列
    • 最优子结构
    • • 代码示例：最长公共子序列
    • 动态规划优化
    • • 斐波那契数列的动态规划版本
      • 最长公共子序列的动态规划版本
  • 2. 动态规划的实现步骤
  • 3. 动态规划的典型应用
  • • 示例1：斐波那契数列
    • • 递归实现（效率低，存在大量重复计算）：
      • 动态规划实现（效率高，避免重复计算）：
    • 示例2：背包问题
    • • 状态定义：
      • 状态转移方程：
      • 代码实现：
  • 4. 动态规划的特点
  • 5. 总结

052. 理解动态规划的基本概念

动态规划（Dynamic Programming，简称DP）是一种解决复杂问题的算法思想，它通过将问题分解为更小的子问题，并将子问题的解存储起来（通常使用表格或数组），避免重复计算，从而提高算法的效率。动态规划特别适用于具有重叠子问题和最优子结构的问题。

1. 动态规划的基本概念

1.1 最优子结构

如果一个问题的最优解包含其子问题的最优解，则称该问题具有最优子结构。这意味着可以通过求解子问题的最优解来构建原问题的最优解。

1.2 重叠子问题

在递归求解过程中，如果某些子问题被多次重复计算，则称该问题具有重叠子问题。动态规划通过存储这些子问题的解，避免了重复计算，从而提高了效率。

1.3 状态和状态转移方程

• 状态：动态规划中的状态通常是一个变量或一组变量，用于描述问题的某个阶段的状态。状态的选择需要满足无后效性，即当前状态的决策只依赖于当前状态，而不依赖于之前的状态。

• 状态转移方程：描述状态之间的关系，即如何从一个状态转移到另一个状态。状态转移方程是动态规划的核心，它决定了如何通过子问题的解来构建原问题的解。

重叠子问题

重叠子问题是指在递归算法中，同一个子问题被多次计算。动态规划通过存储这些子问题的解，避免重复计算，从而提高效率。重叠子问题通常出现在递归算法中，如斐波那契数列、背包问题等。

代码示例：斐波那契数列

#include int fib(int n) {  if (n <= 1) return n; return fib(n-1) + fib(n-2);}int main() {  int n = 10; printf(\"Fibonacci number is %d\\n\", fib(n)); return 0;}

在这个例子中，fib(n-1) 和 fib(n-2) 会多次计算相同的子问题，导致效率低下。

最优子结构

最优子结构是指一个问题的最优解包含其子问题的最优解。动态规划通过将问题分解为子问题，并利用子问题的最优解来构造原问题的最优解。最优子结构通常出现在最优化问题中，如最短路径、最长公共子序列等。

代码示例：最长公共子序列

#include #include int max(int a, int b) {  return (a > b) ? a : b;}int lcs(char *X, char *Y, int m, int n) {  if (m == 0 || n == 0) return 0; if (X[m-1] == Y[n-1]) return 1 + lcs(X, Y, m-1, n-1); else return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));