C++中如何实现动态规划算法_动态规划问题解析-C++-PHP中文网

C++中如何实现动态规划算法_动态规划问题解析

尼克

发布： 2025-06-18 09:18:02

原创

290人浏览过

c++中如何实现动态规划算法_动态规划问题解析

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

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

解决方案

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

立即学习“C++免费学习笔记（深入）”；

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

#include <iostream>
#include <vector>

using namespace std;

int solve(int i, int j, vector<vector<int>>& 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<vector<int>> dp(n + 1, vector<int>(m + 1, -1)); // 初始化为-1，表示未计算
    cout << solve(n, m, dp) << endl;
    return 0;
}

登录后复制

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

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n = 5, m = 6;
    vector<vector<int>> dp(n + 1, vector<int>(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;
}

登录后复制

动态规划的难点在于：

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

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

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

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

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

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

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

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

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