常见面试题--动态规划介绍（附C++源码实现）

关注我，持续分享逻辑思维&管理思维； 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导；
有意找工作的同学，请参考博主的原创：《面试官心得--面试前应该如何准备》，《面试官心得--面试时如何进行自我介绍》， 《做好面试准备，迎接2024金三银四》。
【图解《程序员面试常见的十大算法》及代码实现】

-------------------------------------正文----------------------------------------

动态规划算法，是一种在数学、计算机科学、和经济学中用于优化多阶段决策过程的算法。它的基本思想是将问题分解成若干个子问题，先求解子问题，并将这些子问题的解存储起来，以便在解决更大问题时重用，从而避免重复计算。动态规划算法适用于具有重叠子问题和最优子结构性质的问题，这类问题在分解后得到的子问题往往不是互相独立的，而是存在依赖关系。动态规划算法的时间复杂度通常低于朴素解法，因为它通过记忆化存储已经解决的子问题的答案来减少计算量。

动态规划算法的特点包括：
重叠子问题：在求解过程中，相同的子问题可能会被多次计算。动态规划通过保存已解决的子问题的答案来避免重复计算。
最优子结构：如果问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质。这为动态规划算法提供了重要线索。
填表格式：动态规划算法使用一个表格来记录所有已解的子问题的答案，这个表格被称为状态表或动态规划表。
动态规划算法的应用非常广泛，例如在背包问题、上楼梯问题等场景中都有应用。通过将一个大问题分解成若干个小问题，并逐步解决这些小问题，最终得到原问题的解。

以下是一个简单的动态规划（DP）问题的C++实现例子，例子中解决的是子序列和问题。
问题描述：给定一个整数序列，找出其中和最大的非空子序列。

#include <iostream>
#include <vector>
 
using namespace std;
 
int maxSubsequenceSum(const vector<int>& seq) {
    int maxSum = seq[0], currentSum = maxSum;
    for (int i = 1; i < seq.size(); ++i) {
        currentSum = max(seq[i], currentSum + seq[i]);
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}
 
int main() {
    vector<int> seq = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; // 例子序列
    cout << "最大子序列和为: " << maxSubsequenceSum(seq) << endl;
    return 0;
}

再来看上面提到的背包问题：
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i]
。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

#include <iostream>
#include <vector>
using namespace std;
 
// 动态规划解决背包问题
vector<int> knapsack(int W, vector<int>& weight, vector<int>& value) {
    int n = weight.size();
    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 (weight[i - 1] <= j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
 
    // 打印最终的背包内物品的最大价值
    cout << "最大价值: " << dp[n][W] << endl;
 
    // 构造解决方案
    vector<int> solution;
    for (int i = n, j = W; i > 0; --i) {
        if (dp[i][j] > dp[i - 1][j]) {
            solution.push_back(i);
            j -= weight[i - 1];
        }
    }
 
    return solution;
}
 
int main() {
    int W; // 背包的总重量
    vector<int> weight = {2, 1, 3}; // 物品的重量
    vector<int> value = {3, 2, 4};  // 物品的价值
 
    // 用户输入背包的总重量
    cout << "请输入背包的总重量: ";
    cin >> W;
 
    // 调用动态规划函数
    vector<int> solution = knapsack(W, weight, value);
 
    // 打印解决方案
    cout << "解决方案: ";
    for (int i : solution) {
        cout << i << " ";
    }
    cout << endl;
 
    return 0;
}

感兴趣的同学辛苦 关注/点赞 ，持续分享逻辑、算法、管理、技术、人工智能相关的文章。

博主其它经典原创：《管理心得--如何高效进行跨部门合作》，《技术心得--如何成为优秀的架构师》、《管理心得--如何成为优秀的架构师》、《管理心理--程序员如何选择职业赛道》，及
《C#实例：SQL如何添加数据》，《C#实战分享--爬虫的基础原理及实现》欢迎大家阅读