动态规划(DP)经典算法——整数分解、最大连续子序列和、合唱队形(最长递增子序列)、最长公共子序列、AOE网络最长路径（关键活动）、弗洛伊德算法（两点间距离最短）、0/1背包问题_dp算法

目录

一、概述

二、具体算法

1.整数分解

2.最大连续子序列和 

3.合唱队形

4.最长公共子序列

5.AOE网络（最长路径） 

6.弗洛伊德算法（两点间距离最短）

7.0/1背包

7.1 递推公式（不考代码，考自己推算时）

 7.2 算法解

---

一、概述

动态规划的基本要素：

最优子结构性质、重叠子问题性质

动态规划：

把多阶段问题转换为一系列的相互联系的单阶段问题，逐 个加以解决。所以，DP实际上是一种数学方法，是求解某类 问题的方法，严格意义上不是一种算法。

适合动态规划求解的问题：

1. 具有最优子结构：原问题的最优解包含子问题的最优解

2. 有重叠子问题：子问题之间不独立，一个子问题在下一阶段决策中可能被多次使用到。

3. 无后效性：某阶段状态一旦确定，就不受这个状 态以后决策的影响

动态规划求解问题步骤：

1. 分析问题的最优子结构，将大问题转换为小问题（状态转移）

2.  递归的定义最优解（状态转移方程或递归方程，确定 dp含义）。

3.  以自底向上或自顶向下（备忘录法）的记忆化方式计 算出最优值。

4.  根据计算最优值时得到的信息，构造问题最优解。

注：动态规划是自底向上，备忘录方法是自顶向下

---

二、具体算法

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;
            else
                dp[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><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]=0
        dp[i][0] = 0;
    for (j = 0; j <= W; j++) // 置边界条件dp[0][j]=0
        dp[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];
            else
                dp[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;          // 选取物品i
            maxValue_sum += v[i]; // 累计总价值
            r = r - w[i];
        }
        else
            flag[i] = 0;          // 不选取物品i
        i--;
    }
}
 
int main()
{
    dp_arr();
    Buildx();
    for (int i = 0; i < 6; i++)
        cout << flag[i] << " ";
}

运行结果：0 1 1 0 1 0

---

注：

为了应对考试，后面有的没有写算法，只写了自己手动该怎么解，详情算法之后更新，或可自行搜索 ~~