关注我，持续分享逻辑思维&管理思维； 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导；
有意找工作的同学，请参考博主的原创：《面试官心得--面试前应该如何准备》，《面试官心得--面试时如何进行自我介绍》， 《做好面试准备，迎接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#实战分享--爬虫的基础原理及实现》欢迎大家阅读