✨博主:命运之光 🦄专栏:算法修炼之练气篇 🍓专栏:算法修炼之筑基篇 ✨博主的其他文章:点击进入博主的主页 前言:学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了,下来我们进阶到算法修炼之筑基篇的学习。筑基期和练气期难度可谓是天差地别,懂得都懂,题目难度相比起练气期的题目难度提升很多,所以要是各位蒟蒻小伙伴们看不懂筑基期的题目可以在练气期多积累积累,练气期的题目也会不断更新,大家一定要把基础打牢固了再来看筑基期的题目哈,这样子也可以提高大家的学习效率,一举两得,加油(●'◡'●)🎉🎉
动态规划(Dynamic Programming)是一种解决优化问题的算法思想,通常用于解决具有重叠子问题性质和最优子结构性质的问题。动态规划将问题分解成一系列重叠的子问题,并通过保存子问题的解来避免重复计算,从而提高算法的效率。
下面是一般解决动态规划问题的步骤:
1. 确定问题的状态:将原问题划分为若干个子问题,确定每个子问题的状态,状态一般由一些变量表示。
2. 定义状态转移方程:根据子问题之间的关系,建立状态之间的转移方程。这个转移方程描述了问题的最优解与子问题的最优解之间的关系。
3. 初始化:确定初始状态的值,一般是边界情况下的解,或者根据题目要求进行初始化。
4. 确定计算顺序:根据状态转移方程,确定计算状态的顺序。通常,需要先计算较小规模的子问题,再逐步计算规模较大的子问题。
5. 递推计算:按照计算顺序,通过状态转移方程逐步计算每个状态的值。
6. 求解原问题:根据子问题的解或最终状态的值,求解原问题的最优解。
7. 可选的优化:有些情况下,可以通过一些技巧进行进一步的优化,例如使用滚动数组、空间压缩等方法来降低空间复杂度。
总的来说,动态规划是一种自底向上的求解方法,通过将原问题拆解为子问题并利用子问题的解来求解原问题的最优解。以上是一般解决动态规划问题的步骤,具体问题需要根据实际情况进行调整和优化。
在使用C/C++编写动态规划算法时,以下是一些常见的套路和技巧:
总的来说,C/C++编写动态规划算法时,需要熟悉数组的定义和操作,灵活运用循环结构和条件语句,并注意处理边界情况和选择合适的循环顺序。对于大规模问题,可能需要考虑空间优化技巧。根据问题的具体要求,进行相应的算法设计和实现。
总的来说,学好动态规划需要理解其基本概念和思想,并在实践中不断积累经验。通过解决各种不同类型的动态规划问题,可以提高对动态规划算法的理解和应用能力。
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length();
int n = text2.length();
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 (text1[i - 1] == text2[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 lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0);
dp[0] = nums[0];
int maxSum = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = max(nums[i], dp[i - 1] + nums[i]);
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
int matrixChainMultiplication(vector<int>& dimensions) {
int n = dimensions.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len < n; len++) {
for (int i = 0; i < n - len; i++) {
int j = i + len;
dp[i][j] = INT_MAX;
for (int k = i + 1; k < j; k++) {
int cost = dp[i][k] + dp[k][j] + dimensions[i] * dimensions[k] * dimensions[j];
dp[i][j] = min(dp[i][j], cost);
}
}
}
return dp[0][n - 1];
}
void shortestPath(vector<vector<int>>& graph) {
int n = graph.size();
vector<vector<int>> dp(graph);
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dp[i][k] != INT_MAX && dp[k][j] != INT_MAX) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
}
}
int cuttingRod(vector<int>& prices, int length) {
int n = prices.size();
vector<int> dp(length + 1, 0);
for (int i = 1; i <= length; i++) {
for (int j = 1; j <= i; j++) {
dp[i] = max(dp[i], prices[j - 1] + dp[i - j]);
}
}
return dp[length];
}
int editDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;
}
}
}
return dp[m][n];
}
🍓🍓动态规划是一种令人兴奋和有趣的算法思想,通过将问题分解为子问题并保存子问题的解,我们可以高效地求解复杂问题的最优解。在本篇博客中,我们探讨了几种常见的动态规划问题,包括最长公共子序列、最长递增子序列、最大子数组和、矩阵链相乘、最短路径问题、切割钢条问题和字符串编辑距离。对于每个问题,我们提供了解题思路、通用状态方程和标准模板。 🍓🍓希望这篇博客能够让你对动态规划有一个简单而全面的了解,并且激发你在解决问题时尝试动态规划的勇气。记住,在解决动态规划问题时,关键是理解问题的性质和定义状态,然后设计合适的状态转移方程。通过不断学习和练习,你将掌握动态规划的技巧,能够灵活地应对各种问题。 🍓🍓让我们一起享受动态规划的大冒险吧!愿你在解题过程中充满欢乐和成就感。继续保持好奇心,不断探索新的解题方法和技巧,你将在编程的旅程中取得更多的成就。 感谢你的阅读,希望这篇博客对你有所帮助。祝你在动态规划的世界中玩得开心,继续热爱编程!