当前位置：首页 > article >正文

动态规划模式

article 2025/1/5 13:05:49

动态规划（Dynamic Programming, DP）是一种解决复杂问题的算法设计技术，它通过将大问题分解为小问题，并利用小问题的解决方案来构造大问题的解决方案，从而避免了重复计算。动态规划通常用于具有“最优子结构”和“重叠子问题”特征的问题。

动态规划的基本步骤

定义状态：明确问题的状态表示。即如何用状态表示当前的子问题。
状态转移方程：根据问题的结构，找到从一个状态转移到另一个状态的方式。
初始化：为基础情况设置初始值。
计算顺序：确定计算的顺序，从最小的子问题开始逐步计算到原问题。
答案提取：从动态规划表中提取最终答案。

动态规划的典型应用场景

最短路径问题（如 Dijkstra、Floyd 算法）。
背包问题（如 0/1 背包、完全背包）。
字符串匹配问题（如最长公共子序列、编辑距离）。
最优子结构问题（如矩阵链乘法问题、切割钢条问题）。

动态规划的分类

动态规划的算法通常可以分为以下两种类型：

自顶向下的递归式动态规划（Top-Down with Memoization）：

使用递归进行问题的求解，并通过记忆化（Memoization）保存已计算的结果，避免重复计算。

自底向上的迭代式动态规划（Bottom-Up with Tabulation）：

通过迭代从最小子问题开始，逐步解决更大的子问题，直到得到最终结果。

动态规划的三大特点

最优子结构：问题的最优解可以通过子问题的最优解来构造。例如，最长公共子序列问题的最优解可以通过子问题的解来构造。
重叠子问题：不同的子问题可能会多次出现，因此可以通过记忆化来存储已解决的子问题，避免重复计算。
状态转移：通过当前状态和已解决的子问题来推导出下一个状态。

动态规划的经典问题

1. 0/1 背包问题

问题描述：

有一个背包，最多可以容纳重量为 W 的物品。
有 n 个物品，每个物品的重量是 w[i]，价值是 v[i]。
问：如何选择物品，使得背包的总价值最大，且总重量不超过 W？

动态规划解法：

定义状态 dp[i][j]：表示前 i 个物品，背包容量为 j 时的最大价值。
状态转移方程：
- 如果不选择第 i 个物品：dp[i][j] = dp[i-1][j]
- 如果选择第 i 个物品：dp[i][j] = dp[i-1][j-w[i]] + v[i]
- 最终的状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int knapsack(int W, vector<int>& w, vector<int>& v, int n) {
    // dp[i][j]表示前i个物品，容量为j时的最大价值
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (w[i - 1] <= j) {
                // 当前物品不放入或放入两种选择的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j]; // 当前物品不能放入
            }
        }
    }
    return dp[n][W]; // 返回最大价值
}

int main() {
    int W = 10; // 背包容量
    vector<int> w = {2, 3, 4, 5}; // 物品重量
    vector<int> v = {3, 4, 5, 6}; // 物品价值
    int n = w.size();

    cout << "Max value in knapsack: " << knapsack(W, w, v, n) << endl;
    return 0;
}

输出：

Max value in knapsack: 7

2. 最长公共子序列问题

问题描述：

给定两个字符串 s1 和 s2，求它们的最长公共子序列（LCS）。

动态规划解法：

定义状态 dp[i][j]：表示 s1[0...i-1] 和 s2[0...j-1] 的最长公共子序列长度。
状态转移方程：
- 如果 s1[i-1] == s2[j-1]，那么 dp[i][j] = dp[i-1][j-1] + 1
- 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[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]; // 返回最长公共子序列长度
}

int main() {
    string s1 = "abcde";
    string s2 = "ace";

    cout << "Length of Longest Common Subsequence: " << longestCommonSubsequence(s1, s2) << endl;
    return 0;
}

输出：

Length of Longest Common Subsequence: 3

3. 斐波那契数列

斐波那契数列是经典的动态规划问题。其定义是：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

动态规划解法通过迭代避免了递归中的重复计算。

#include <iostream>
using namespace std;

int fib(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

int main() {
    int n = 10;
    cout << "Fibonacci of " << n << " is " << fib(n) << endl;
    return 0;
}