正文

掌握C++动态规划，从实战案例学起

/0 浏览量
0619

动态规划是一种重要的算法思想，尤其在解决优化问题、序列问题等方面表现出色。C++作为一种高效、灵活的编程语言，非常适合用来实现动态规划算法。本文将通过一系列实战案例，带你深入了解C++动态规划，让你在实践中掌握这一技巧。

动态规划基础

在深入实战之前，我们先回顾一下动态规划的基本概念。

动态规划的核心思想是将复杂问题分解为若干个相互重叠的子问题，并存储这些子问题的解，避免重复计算。动态规划通常包含以下步骤：

  1. 确定状态：定义问题中的状态变量，这些变量表示问题的部分解。
  2. 状态转移方程：描述状态之间的关系，即如何从已知的状态得到新的状态。
  3. 边界条件：定义问题的初始状态或终止状态。
  4. 计算顺序：确定求解的顺序，通常是按照问题的规模从大到小或从小到大计算。

实战案例一：最长公共子序列（LCS）

最长公共子序列问题是一个经典的动态规划问题。给定两个字符串，找出它们的最长公共子序列。

状态定义：设dp[i][j]表示字符串str1[0...i-1]和str2[0...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])。

代码示例：

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

int longestCommonSubsequence(const string& str1, const string& str2) {
    int m = str1.size(), n = str2.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 (str1[i - 1] == str2[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 str1 = "ABCDGH";
    string str2 = "AEDFHR";
    cout << "最长公共子序列长度：" << longestCommonSubsequence(str1, str2) << endl;
    return 0;
}

实战案例二：背包问题

背包问题是一个典型的优化问题，通常分为0/1背包和完全背包问题。

0/1背包问题：给定一组物品，每个物品有一个重量和价值，背包有一个最大承重，求装入背包的物品价值总和最大。

状态定义：设dp[i][w]表示从前i个物品中选择，使背包容量为w时的最大价值。

状态转移方程：

  • 如果i个物品的总重量小于等于w，则dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])；
  • 否则，dp[i][w] = dp[i-1][w]。

代码示例：

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

int knapsack(const vector<int>& weights, const vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int w = 1; w <= W; ++w) {
            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];
}

int main() {
    vector<int> weights = {1, 2, 4};
    vector<int> values = {3, 4, 5};
    int W = 5;
    cout << "最大价值：" << knapsack(weights, values, W) << endl;
    return 0;
}

总结

通过以上两个实战案例，我们可以看到动态规划在解决实际问题中的强大能力。掌握动态规划，需要不断练习和积累经验。希望本文能帮助你更好地理解C++动态规划，让你在实践中不断提升。

-- 展开阅读全文 --