序列和、合唱队形(最长递增子序列)、最长公共子序列、AOE网络最长路径（关键活动）、弗洛伊德算法（两点间距离最短）、0/1背包问题"/>
动态规划(DP)经典算法——整数分解、最大连续子序列和、合唱队形(最长递增子序列)、最长公共子序列、AOE网络最长路径（关键活动）、弗洛伊德算法（两点间距离最短）、0/1背包问题
目录
一、概述
二、具体算法
1.整数分解
2.最大连续子序列和
3.合唱队形
4.最长公共子序列
5.AOE网络（最长路径）
6.弗洛伊德算法（两点间距离最短）
7.0/1背包
7.1 递推公式（不考代码，考自己推算时）
7.2 算法解
一、概述
动态规划的基本要素：
最优子结构性质、重叠子问题性质
动态规划：
把多阶段问题转换为一系列的相互联系的单阶段问题，逐 个加以解决。所以，DP实际上是一种数学方法，是求解某类 问题的方法，严格意义上不是一种算法。
适合动态规划求解的问题：
具有最优子结构：原问题的最优解包含子问题的最优解
有重叠子问题：子问题之间不独立，一个子问题在下一阶段决策中可能被多次使用到。
无后效性：某阶段状态一旦确定，就不受这个状 态以后决策的影响
动态规划求解问题步骤：
分析问题的最优子结构，将大问题转换为小问题（状态转移）
递归的定义最优解（状态转移方程或递归方程，确定 dp含义）。
以自底向上或自顶向下（备忘录法）的记忆化方式计 算出最优值。
根据计算最优值时得到的信息，构造问题最优解。
注：动态规划是自底向上，备忘录方法是自顶向下
二、具体算法
1.整数分解
状态转移方程：
根据状态转移方程写出具体算法：
#include <iostream>
#include <algorithm>
#define MAXN 10
using namespace std;//dp做记忆数组，存放计算过的数字，下次直接拿来用，以避免重复计算
int dp[MAXN][MAXN];
int split_num(int n, int k)
{if (dp[n][k] != 0)return dp[n][k];if (n == 1 || k == 1){dp[n][k] = 1;return dp[n][k];}else if (n < k){dp[n][k] = split_num(n, n);return dp[n][k];}else if (n == k){dp[n][k] = split_num(n, n - 1) + 1;return dp[n][k];}else{dp[n][k] = split_num(n, k - 1) + split_num(n - k, k);return dp[n][k];}
}int main()
{int ans = split_num(5, 5);cout << ans;
}结果是 7
2.最大连续子序列和
dp[n]中，最大值下标记为max_index,在dp数组中，从该位置向前找，找到第一个 dp值小于或等于0的元素dp[k],则a序列中从第k+1--max_index位置的元素和构成了该序列的最大连续子序列的和。
dp[0] = 0
dp[n] = max{dp[n - 1] + a[n] ,a[n]};
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100
// dp[n]数组记录[0...n]的序列和
int dp[MAXN];
// a数组
int a[] = {0, -2, 11, -4, 13, -5, -2};
int n = 6;// 求解dp数组
void dp_sub()
{dp[0] = 0;for (int i = 1; i <= n; i++)dp[i] = max(dp[i - 1] + a[i], a[i]);
}int dp_max_sub()
{int max_index = 1;// 求解dp中最大元素dp[max_index]for (int i = 2; i <= n; i++)if (dp[i] > dp[max_index])max_index = i;// 向前遍历找到第一个<= 0的(输出子序列用)int tmp; // 记录i值for (int i = max_index; i > 0; i--){if (dp[i] <= 0)break;tmp = i;}// 输出子序列cout << "所选子序列为：";for (int j = tmp; j <= max_index; j++)cout << a[j] << " ";cout << endl;return dp[max_index];
}int main()
{dp_sub();int ans = dp_max_sub();cout << "最大子序列和为：" << ans;
}所选子序列为：11 -4 13
最大子序列和为：20
3.合唱队形
首先来复习如何求解最递增长子序列长度：
下列代码先给出最长递增子序列的算法
#include <iostream>
#include <algorithm>
using namespace std;/*
先学习一下最长递增子序列怎么求
*/int dp[100];// 最长递增子序列
int max_up_arr(int a[], int n)
{for (int i = 0; i < n; i++){dp[i] = 1;for (int j = 0; j < i; j++){// 新加入的a[i]比上一个数a[j]大if (a[i] > a[j])dp[i] = max(dp[i], dp[j] + 1);}}// 找出dp中最大值即为最长递增子序列的长度int ans = dp[0];for (int i = 1; i < n; i++)ans = max(ans, dp[i]);return ans;
}int main()
{int a[] = {2, 1, 5, 3, 6, 4, 8, 9, 7};int n = 9;int ans = max_up_arr(a, n);cout << ans;
}
下面给出合唱队形的解决方案
思路： 寻找一个同学，其左边同学的身高递增序列+其右边同学的身高递减序列是最长的。 原问题转换为求最长递增序列长度和最长递减序列长度，两者相加再减1，即可得到整个合唱队形的长度。
int f1[maxn];//最大上升子序列
int f2[maxn];//最大下降子序列int sing_team(int n, int a[100])
{ // 从左到右求最大上升子序列for (int i = 1; i <= n; i++){f1[i] = 1;for (int j = 1; j < i; j++)if (a[j] < a[i] && f1[i] < f1[j] + 1)f1[i] = f1[j] + 1;}// 从右到左求最大下降子序列for (int i = n; i >= 1; i--){f2[i] = 1;for (int j = i + 1; j <= n; j++)if (a[j] < a[i] && f2[i] < f2[j] + 1)f2[i] = f2[j] + 1;}int ans = 0;//枚举中间最高值for (int i = 1; i <= n; i++)if (ans < f1[i] + f2[i] - 1)ans = f1[i] + f2[i] - 1; return ans;
}int main()
{int a[] = {176, 163, 150, 180, 170, 130, 167, 160};int n = 8;int ans = sing_team(n, a);cout << ans;
}4.最长公共子序列
求dp的状态转移方程为：
dp[i][j] = 0 i = 0 或 j = 0
dp[i][j] = dp[i - 1][j - 1] + 1 a[i - 1] = b[j -1]
dp[i][j] = MAX(dp[i][j - 1]，dp[i - 1][j]) a[i -1] ≠ b[j - 1]
下面给出非算法解题过程：
根据左侧矩阵写出右侧矩阵；右侧矩阵根据213原则，公共子序列为斜箭头的箭头尾相连
算法实现：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 50// a序列和b序列
string a, b;
// ab序列的长度
int m = 6;
int n = 9;// dp数组
int dp[MAX][MAX];
// 存放公共子序列
vector<char> pub;// 根据状态转移方程计算dp数组
void dp_arr()
{for (int i = 0; i <= m; i++)dp[i][0] = 0;for (int j = 0; j <= n; j++)dp[0][j] = 0;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++){if (a[i - 1] == b[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}
}// 由dp数组构造公共子序列
void build_pub()
{// k表示a,b数组最长公共子序列长度int k = dp[m][n];int i = m;int j = n;while (k > 0){// 与左边元素不同if (dp[i][j] == dp[i - 1][j])i--;// 与右边元素不同else if (dp[i][j] == dp[i][j - 1])j--;// 左右两边均不相同，假如公共子序列中else{pub.push_back(a[i - 1]);i--;j--;k--;}}
}int main()
{a = "abcbdb";b = "acbbabdbb";dp_arr();build_pub();for (int i = 0; i < pub.size(); i++)cout << pub[i] << " ";
}运行结果：b d b c a
时间复杂度为O(m×n)
空间复杂度为O(m×n)
5.AOE网络（最长路径）
earlist[i]:最早发生时间 源点s到汇点t的最长路径
lastest[j]:最晚发生时间 前一个结点的最晚发生时间 - 活动时间
lastest[i] - earlist[j] = w[i][j] 正好等于权重，关键活动（边）
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| earliest(i) | 0 | 6 | 4 | 5 | 7 | 7 | 16 | 15 | 19 |
| lastest(i) | 0 | 6 | 6 | 9 | 7 | 11 | 17 | 15 | 19 |
| 减 | 0 | 0 | 0 | 0 | 0 |
关键活动：<0,1><1,4><4,7><7,8>
关键路径：0 1 4 7 8
6.弗洛伊德算法（两点间距离最短）
引入一个新结点k 取原来路径度与引用后曲折相加后路径长度的min
7.0/1背包
7.1 递推公式（不考代码，考自己推算时）：
依次列举即可
这里是一个up主的教学视频截图：
结果为15
7.2 算法解如下：
物品i不被装入则 dp[i][r] = dp[i - 1][r];
物品i被装入则 dp[i][r] = dp[i - 1][r - w[i]] + v[i];
dp[i][r] = MAX{ dp[i -1][r] , dp[i - 1][r - w[i]] + v[i] }
#include <iostream>
#include <algorithm>
using namespace std;int n = 5, W = 10; // 5种物品，限制重量不超过10
int w[] = {0, 2, 2, 6, 5, 4}; // 下标0不用
int v[] = {0, 6, 3, 5, 4, 6}; // 下标0不用// 定义dp数组
int dp[6][6];
int flag[6]; // 表示是否被装入
int maxValue_sum; // 存放最优解的总价值// 先求出dp数组
void dp_arr()
{int i, j;for (i = 0; i <= n; i++) // 置边界条件dp[i][0]=0dp[i][0] = 0;for (j = 0; j <= W; j++) // 置边界条件dp[0][j]=0dp[0][j] = 0;for (i = 1; i <= n; i++){for (j = 1; j <= W; j++)if (j < w[i])dp[i][j] = dp[i - 1][j];elsedp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);}
}// 回推最优解
void Buildx()
{int i = n, r = W;maxValue_sum = 0;while (i >= 0){if (dp[i][r] != dp[i - 1][r]){flag[i] = 1; // 选取物品imaxValue_sum += v[i]; // 累计总价值r = r - w[i];}elseflag[i] = 0; // 不选取物品ii--;}
}int main()
{dp_arr();Buildx();for (int i = 0; i < 6; i++)cout << flag[i] << " ";
}运行结果：0 1 1 0 1 0
注：
为了应对考试，后面有的没有写算法，只写了自己手动该怎么解，详情算法之后更新，或可自行搜索 ~~
更多推荐
动态规划(DP)经典算法——整数分解、最大连续子序列和、合唱队形(最长递增子序列)、最长公共子序列、AOE网络最长路径（关键活动）、弗洛伊德算法（两点间距离最短
发布评论