经典动态规划问题

动态规划（Dynamic Programming，DP）是一种用于解决复杂问题的方法，尤其适用于那些可以分解为相对简单的子问题的问题。其基本思想是通过将问题分解为更小的子问题，并将这些子问题的结果进行储存和重用，从而减少重复计算，提高算法效率。动态规划的核心思想可以概括为以下几个步骤：

1. 划分子问题：将原问题分解为若干个相互重叠的子问题。这个过程通常会基于问题的结构，找到一种递归的关系，将大问题拆解成小问题。

2. 定义状态：确定问题的状态。状态通常是描述问题在某一步骤的特征，可以用一个或多个变量表示。例如，在求解最短路径问题时，状态可以是当前节点和已经经过的节点集合。

3. 确定状态转移方程：找到状态之间的关系，即状态转移方程。状态转移方程描述了如何从一个状态转移到另一个状态，以及这些状态之间的递归关系。

4. 确定初始状态和边界条件：明确初始状态和边界条件。初始状态是问题的起始点，边界条件是一些已知的简单解。

5. 自底向上计算：从最简单的子问题开始，逐步计算并储存每个子问题的结果。最终，通过组合这些子问题的解，得到原问题的解。

6. 储存和重用子问题的结果：利用一个表格（通常是数组或矩阵）来储存已经计算过的子问题的结果，以便在需要时直接使用，避免重复计算。

01背包问题

问题描述： 给定一组物品，每个物品有一个重量和一个价值，另有一个背包，它的容量为限定的重量。目标是找出一个物品的子集，使得这些物品的总重量不超过背包的容量，并且它们的总价值最大。

动态规划解法：

1. 状态定义：

   • 用 dp[i][w] 表示前 i 个物品中可以放入一个容量为 w 的背包的最大价值。

2. 状态转移方程：

   • 如果不选择第 i 个物品：dp[i][w] = dp[i-1][w]
   • 如果选择第 i 个物品：dp[i][w] = dp[i-1][w-weight[i-1]] + value[i-1]
   • 综合两种情况：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1])

3. 初始化：

   • 当没有物品或容量为0时，dp[0][w] = 0 和 dp[i][0] = 0

4. 结果：

   • 最终结果在 dp[n][W]，其中 n 是物品的数量，W 是背包的容量。

伪代码：

Algorithm 0_1_Knapsack(values, weights, W)
    n = length(values)
    dp = array[n+1][W+1]
    
    for i from 0 to n:
        for w from 0 to W:
            if i == 0 or w == 0:
                dp[i][w] = 0
            else if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

最长公共子序列问题（LCS）

问题描述： 给定两个字符串，求它们的最长公共子序列的长度。公共子序列是不需要连续但保持相对顺序的子串。

动态规划解法：

1. 状态定义：

   • 用 dp[i][j] 表示字符串 X 的前 i 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。

2. 状态转移方程：

   • 如果 X[i-1] == Y[j-1]：dp[i][j] = dp[i-1][j-1] + 1
   • 如果 X[i-1] != Y[j-1]：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3. 初始化：

   • 当 i 或 j 为 0 时，dp[i][0] = 0 和 dp[0][j] = 0

4. 结果：

   • 最终结果在 dp[m][n]，其中 m 和 n 分别是字符串 X 和 Y 的长度。

伪代码：

Algorithm LCS(X, Y)
    m = length(X)
    n = length(Y)
    dp = array[m+1][n+1]
    
    for i from 0 to m:
        for j from 0 to n:
            if i == 0 or j == 0:
                dp[i][j] = 0
            else if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]