算法小课堂（四）动态规划-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法小课堂（四）动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、概况

二、背包

2.0闫式dp分析法

2.1 0-1背包

朴素解法

滚动数组

2.2 完全背包

朴素解法

优化降维

滚动数组

2.3完全背包和0-1背包的区别与联系

2.4多重背包问题

朴素解法

二进制枚举优化

贪心算法

单调队列优化

2.5分组背包问题

朴素算法

优化降维

二进制枚举优化

三、线性DP

3.1概述

3.2数字三角形

正序解法

倒序解法

二维优化为一维

记忆化搜索

3.3最长上升子序列

朴素解法

二分查找优化·

回溯路径

记忆化搜索

3.4 最长公共子序列

实验书模板

朴素解法

记忆化搜索递归解法

四、区间DP

4.1概述

4.2石子合并

朴素解法

记忆化搜索

4.3最大子段和

朴素算法

记忆化搜索

递归分治

贪心算法

4.3进阶林大OJ 1443环形最大子段和

4.4最长回文子序列

朴素解法

记忆化搜索

五、计数类DP

5.1 整数划分

编辑

朴素解法

优化成一维

分治解法

记忆化搜索

六、记忆化搜索

6.1滑雪

七、DP优化

7.1矩阵连乘

备忘录方法

记忆化搜索

记忆化搜索与备忘录区别

朴素解法

一、概况

动态规划是一种算法设计技术，它可以有效地解决一些复杂的优化问题。动态规划的主要思想是将原问题分解成若干个子问题进行求解，并将子问题的解缓存起来，避免重复计算，从而达到减少计算量、提高计算效率的目的。

动态规划通常适用于具有以下两个特点的问题：

最优子结构性质：问题的最优解可以由其子问题的最优解推导出来。

重叠子问题性质：问题可以被分解为多个子问题，这些子问题的求解都会重复使用相同的计算过程。

动态规划算法的基本思路可以概括为以下三个步骤：

定义状态：将原问题分解成若干个子问题，定义子问题的解。

状态转移方程：定义子问题之间的递推关系。

边界条件：确定初始状态或边界状态的值。

二、背包

2.0闫式dp分析法

算法小课堂（四）动态规划

闫式动态规划分析法（Yan's DP Analysis Method）是一种系统化的动态规划算法设计方法，由计算机科学家闫学灿于1993年提出。该方法将动态规划问题分解为子问题，并通过归纳法推导出状态转移方程，从而构造出整个问题的解。

具体来说，闫式dp分析法包含以下步骤：

定义状态：根据问题的特点，定义出状态变量，通常是一个或多个变量，代表问题中的某些量，如长度、位置、状态等。

定义状态转移方程：根据问题的特点，通过归纳法推导出状态转移方程，即如何从当前状态转移到下一个状态。在推导状态转移方程时，需要考虑状态的边界和状态转移的约束条件。

确定初始状态：根据问题的特点，确定初始状态，通常是问题的边界条件。

确定最终状态：根据问题的特点，确定最终状态，即问题的解。

计算解：根据状态转移方程，通过动态规划算法计算问题的解。

闫式dp分析法的优点是系统化、规范化，能够使动态规划算法的设计更加清晰、简单、易于实现。该方法常用于算法竞赛中，特别是动态规划类问题的解决。

2.1 0-1背包

有 N件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi用空格隔开，分别表示第 i件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000
0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

朴素解法

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值

int main()
{
    int n, m;
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i])
                f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;

    return 0;
}

滚动数组

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值
int f[MAXN];    // f[i][j]体积下前i个物品的最大价值

int main()
{
    int n, m;
    cin >> n >> m;  // 输入物品个数和背包容量

    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];    // 输入第i个物品的体积和价值

    // 进行01背包动态规划
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= v[i]; j--)   // 从大到小枚举体积
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);   // 取当前状态和加上第i个物品的最大价值中的最大值
        }

    cout << f[m] << endl;   // 输出背包容量为m时的最大价值

    return 0;
}

2.2 完全背包

完全背包问题是指有一个容量为V的背包，和N个体积为v[i]，价值为w[i]的物品，每个物品可以选取无限次，问如何选择物品放入背包，使得背包中的物品总价值最大。

对于完全背包问题，与01背包问题的状态转移方程不同，其状态转移方程为：

f[i][j] = max(f[i-1][j], f[i][j-v[i]]+w[i])

算法小课堂（四）动态规划

有 N 种物品和一个容量是 V的背包，每种物品都有无限件可用。

第 i种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000
0<vi,wi≤1000

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10

朴素解法

#include<iostream>
using namespace std;
const int N = 1010;

int f[N][N];  // f[i][j]表示前i个物品，背包容量为j时的最大价值
int v[N], w[N];  // v[i]表示第i个物品的体积，w[i]表示第i个物品的价值

int main()
{
    int n, m;  // n为物品个数，m为背包容量
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
    }

    // 动态规划过程
    for(int i = 1; i <= n; i++)  // 遍历每个物品
    {
        for(int j = 0; j <= m; j++)  // 枚举背包容量
        {
            for(int k = 0; k * v[i] <= j; k++)  // 枚举第i个物品的数量
            {
                f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
                // f[i][j]表示前i个物品，背包容量为j时的最大价值
                // f[i-1][j-k*v[i]]表示不选第i个物品，背包容量为j-k*v[i]时的最大价值
                // k*w[i]表示选k个第i个物品的价值
                // 取max就是考虑选或不选第i个物品，取最大值
            }
        }
    }

    cout << f[n][m] << endl;  // 输出前n个物品，背包容量为m时的最大价值

    return 0;
}

优化降维

算法小课堂（四）动态规划

#include <iostream>
using namespace std;

const int N = 1010;

int f[N][N]; // f[i][j]表示前i个物品，背包容量为j时的最大价值
int v[N], w[N]; // v[i]表示第i个物品的体积，w[i]表示第i个物品的价值

int main()
{
    int n, m; // n为物品个数，m为背包容量
    cin >> n >> m;

    // 输入每个物品的体积和价值
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    // 动态规划过程
    for (int i = 1; i <= n; i++) { // 遍历每个物品
        for (int j = 0; j <= m; j++) { // 枚举背包容量
            f[i][j] = f[i - 1][j]; // 不选择第i个物品
            if (j >= v[i]) { // 背包容量足够装下第i个物品
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); // 考虑选择第i个物品
            }
        }
    }

    // 输出前n个物品，背包容量为m时的最大价值
    cout << f[n][m] << endl;

    return 0;
}

滚动数组

#include<iostream>
using namespace std;

const int N = 1010;

int f[N]; // f[i]表示背包容量为i时的最大价值
int v[N], w[N]; // v[i]表示第i个物品的体积，w[i]表示第i个物品的价值

int main()
{
    int n, m; // n为物品个数，m为背包容量
    cin >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
    }

    // 动态规划过程
    for(int i = 1; i <= n; i++) // 遍历每个物品
    {
        for(int j = m; j >= v[i]; j--) // 枚举背包容量
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]); // 转移方程
        }
    }

    cout << f[m] << endl; // 输出背包容量为m时的最大价值

    return 0;
}

2.3完全背包和0-1背包的区别与联系

完全背包和0-1背包是背包问题中的两种经典问题，它们的区别和联系如下：

区别：

物品数量限制不同：0-1背包中每个物品只能选择一次，而完全背包中每个物品可以选择无限次。

决策状态转移方程不同：在0-1背包中，对于每个物品，决策只能是放或不放，因此需要分别考虑物品放入和不放入背包两种情况，而在完全背包中，每个物品可以选择多次，因此只需要考虑每个物品放入背包的情况。

联系：

状态转移方程的形式相同：0-1背包和完全背包都可以使用动态规划来求解，它们的状态转移方程都可以写成f(i,j)=max(f(i-1,j),f(i-1,j-w[i])+v[i])的形式。

求解的思路相同：都是通过逐步遍历物品和背包容量，求解每个状态的最优解，最终得到整个问题的最优解。

综上所述，0-1背包和完全背包问题虽然存在一些区别，但它们的解决思路和算法思想都是相似的。

2.4多重背包问题

多重背包问题是背包问题的一种变形，与0-1背包问题和完全背包问题不同的是，每种物品有一个数量限制，不再是仅有一个或无限个可用。

具体来说，给定一个背包容量为C，n种不同的物品，其中第i种物品的体积为v[i]，价值为w[i]，每种物品的数量有一个上限c[i]，现在从这些物品中选择一些装入背包，使得背包的容量不超过C，且所装物品的总价值最大。

多重背包问题可以通过类似于0-1背包问题和完全背包问题的动态规划算法来求解，但需要对状态转移方程进行修改。具体来说，可以将多重背包问题转化为若干个0-1背包问题，每种物品拆分为多个体积相等但价值不同的物品，数量上限即为该物品的可选数量。这样问题就可以被转化为0-1背包问题，采用类似的动态规划算法求解。

多重背包问题也可以使用优化的算法来解决，例如使用单调队列优化的动态规划算法或者基于贪心算法的解法。这些算法能够在保证正确性的同时，减少时间和空间复杂度。

算法小课堂（四）动态规划

有 N种物品和一个容量是 VV 的背包。

第 i种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，N，V用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000
0<vi,wi,si≤1000

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

朴素解法

#include<iostream>
using namespace std;
const int N = 1010;

int f[N][N];  // f[i][j]表示前i个物品，背包容量为j时的最大价值
int v[N], w[N], s[N];  // v[i]表示第i个物品的体积，w[i]表示第i个物品的价值

int main()
{
    int n, m;  // n为物品个数，m为背包容量
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i] >> s[i];
    }

    // 动态规划过程
    for(int i = 1; i <= n; i++)  // 遍历每个物品
    {
        for(int j = 0; j <= m; j++)  // 枚举背包容量
        {
            for(int k = 0; k <= s[i] && k * v[i] <= j; k++)  // 枚举第i个物品的数量
            {
                f[i][j] = max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
                // f[i][j]表示前i个物品，背包容量为j时的最大价值
                // f[i-1][j-k*v[i]]表示不选第i个物品，背包容量为j-k*v[i]时的最大价值
                // k*w[i]表示选k个第i个物品的价值
                // 取max就是考虑选或不选第i个物品，取最大值
            }
        }
    }

    cout << f[n][m] << endl;  // 输出前n个物品，背包容量为m时的最大价值

    return 0;
}

二进制枚举优化

#include<iostream>
using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 体积<M

int main()
{
    cin >> n >> m;
    int cnt = 0; //分组的组别
    for(int i = 1;i <= n;i ++)
    {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1; // 组别里面的个数
        while(k<=s)
        {
            cnt ++ ; //组别先增加
            v[cnt] = a * k ; //整体体积
            w[cnt] = b * k; // 整体价值
            s -= k; // s要减小
            k *= 2; // 组别里的个数增加
        }
        //剩余的一组
        if(s>0)
        {
            cnt ++ ;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }

    n = cnt ; //枚举次数正式由个数变成组别数

    //01背包一维优化
    for(int i = 1;i <= n ;i ++)
        for(int j = m ;j >= v[i];j --)
            f[j] = max(f[j],f[j-v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}

可以通过将多个同种物品拆分成2的幂次个，将其转化为01背包问题。具体来说，将每个物品的数量拆分成若干个2的幂次方（如1,2,4,8），每个幂次对应一种物品，将其看作一个物品组，其中物品组的体积和价值分别为组内所有物品的体积和和价值和，然后使用01背包问题的一维优化来求解最大价值。

具体实现时，首先读入多重背包问题中每个物品的体积、价值和数量，然后将每个物品拆分成2的幂次个，将每个幂次看作一种物品组，将组内所有物品的体积和价值和分别作为该组的体积和价值，最后使用一维的01背包问题求解。

贪心算法

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;

int f[N];  // f[i]表示背包容量为i时的最大价值
int v[N], w[N], s[N];  // v[i]表示第i个物品的体积，w[i]表示第i个物品的价值，s[i]表示第i个物品的数量

int main()
{
    int n, m;  // n为物品个数，m为背包容量
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i] >> s[i];
    }

    // 贪心策略：将多重背包转化为01背包，将每个物品拆分成多个物品
    // 将第i个物品拆分成s[i]个物品，每个物品的体积和价值分别为v[i]和w[i]
    // 这样就将多重背包问题转化为了01背包问题
    for(int i = 1; i <= n; i++)  // 遍历每个物品
    {
        for(int k = 1; k <= s[i]; k *= 2)  // 将第i个物品拆分成多个物品，每次将数量翻倍
        {
            for(int j = m; j >= k * v[i]; j--)  // 枚举背包容量，倒序枚举，防止重复选取
            {
                f[j] = max(f[j], f[j-k*v[i]] + k*w[i]);  // 01背包的动态转移方程
            }
            s[i] -= k;  // 更新第i个物品的数量，减去已经处理的数量
        }
        if(s[i] > 0)  // 处理剩余的物品
        {
            for(int j = m; j >= s[i] * v[i]; j--)
            {
                f[j] = max(f[j], f[j-s[i]*v[i]] + s[i]*w[i]);
            }
        }
    }

    cout << f[m] << endl;  // 输出背包容量为m时的最大价值

    return 0;
}

单调队列优化

#include<bits/stdc++.h>
using namespace std;

const int N = 1005;
const int M = 20005;
int v[N],w[N],s[N]; //体积，价值，数量
int dp[M],g[M], q[M],n,m;

int main(){
    int i,j,k;
    cin>>n>>m;
    for(i = 1;i<=n;i++){
        cin>>v[i]>>w[i]>>s[i];
    }
    for(i = 1;i<=n;i++){
        //枚举v[i]的每个余数
        memcpy(g,dp,sizeof g); //滚动数组优化
        //g表示dp[i-1][],dp表示dp[i][];
        for(j = 0;j<v[i];j++){
            int l = 0,r = 0;
            for(k = j;k<=m;k+=v[i]){
                //维护队列中k到k-s[i]*v[i]的最大值的体积
                //单调队列中最大值存储物品i的数量大于s[i],出队
                if(l<r && (k-q[l+1])/v[i] > s[i]) l++;
                //除去比当前小的元素
                while(l<r && g[k] >= g[q[l+1]] + (k-q[l+1])/v[i]*w[i]) r--;
                q[++r]=k;
                dp[k] = g[q[l+1]]+(k-q[l+1])/v[i]*w[i];
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

单调队列优化的多重背包问题是在多重背包问题的基础上，使用单调队列优化动态规划过程中的状态转移。多重背包问题是一个经典的动态规划问题，其中一个难点在于体积和价值的数量是有限的，需要考虑如何进行状态转移。

传统的多重背包问题使用的是类似01背包问题的动态规划思路，即对于每个物品，将其分解成若干个体积为1的物品，然后使用01背包的方式进行动态规划。但是，这种方法的时间复杂度较高，达到了O(NVM)，其中N、V、M分别为物品数、背包容量和最大数量。

单调队列优化的多重背包问题是在此基础上使用单调队列对状态转移过程进行优化，从而将时间复杂度优化至O(NVlogM)。其主要思路是，将同一件物品拆分成若干个体积为v[i]的物品，然后根据v[i]的余数分成v[i]个子问题。对于每个子问题，使用单调队列维护状态转移过程中的最优解，从而优化状态转移的效率。

具体来说，对于每个物品i，先将dp数组中的值拷贝到g数组中，然后枚举v[i]的每个余数j，并对每个余数j使用单调队列维护状态转移过程中的最优解。由于同一个物品i会分解成v[i]个子问题，因此需要对每个子问题分别进行单调队列优化。

单调队列中存储的是dp[j]加上一定数量的物品i后的最大价值，队列头的元素始终是最优解。在进行状态转移时，将当前状态的价值更新为单调队列中的最大价值即可。

总之，单调队列优化的多重背包问题通过拆分同一件物品并使用单调队列维护状态转移过程中的最优解，将多重背包问题的时间复杂度优化至O(NVlogM)，是一种较为高效的解法。

2.5分组背包问题

分组背包问题是背包问题的一种变种，它的物品被分成了若干组，每组中的物品最多只能选一个，且每组物品只能选一个或不选。求在总体积不超过背包容量的前提下，能获得的最大价值是多少。

具体来说，假设有n个物品，它们被分成了m组，第i组有si个物品，第j个物品的体积为vi,j，价值为wi,j。设f[i][v]表示前i组物品，背包容量为v时能获得的最大价值，则有状态转移方程：

f[i][v] = max(f[i-1][v-kvi,j]+kwi,j) (0<=k<=si,j)

其中vi,j和wi,j分别表示第i组第j个物品的体积和价值。

这个状态转移方程的意义是：在前i-1组物品中，背包容量为v-k*vi,j时的最大价值加上第i组中选取第j个物品k次的价值，可以得到在前i组物品中，背包容量为v时的最大价值

。

实际实现时，可以将每组物品当成一个单独的0-1背包问题，对每个物品都进行一次背包计算，最后累加每组物品所能贡献的最大价值即可

算法小课堂（四）动态规划

有 N组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 N，V用空格隔开，分别表示物品组数和背包容量。

接下来有 NN 组数据：

每组数据第一行有一个整数 Si，表示第 i个物品组的物品数量；

每组数据接下来有 Si 行，每行有两个整数 vij,wij用空格隔开，分别表示第 i 个物品组的第 jj 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000
0<Si≤1000
0<vij,wij≤1000

输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8

朴素算法

#include<bits/stdc++.h>
using namespace std;

const int N=110;
int f[N][N];  //只从前i组物品中选，当前体积小于等于j的最大值
int v[N][N],w[N][N],s[N];   //v为体积，w为价值，s代表第i组物品的个数
int n,m,k;

int main(){
    cin>>n>>m;  //读入物品组数和背包容量
    for(int i=1;i<=n;i++){  //循环读入每组物品信息
        cin>>s[i];  //第i组物品的数量
        for(int j=0;j<s[i];j++){  //循环读入每个物品的体积和价值
            cin>>v[i][j]>>w[i][j];
        }
    }

    for(int i=1;i<=n;i++){  //循环计算最大价值
        for(int j=0;j<=m;j++){  //循环当前背包容量
            f[i][j]=f[i-1][j];  //先不选第i组物品
            for(int k=0;k<s[i];k++){  //循环当前物品组中的物品
                if(j>=v[i][k])     f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);  //如果能放进背包中，则选择放或不放
            }
        }
    }
    cout<<f[n][m]<<endl;  //输出背包容量为m时的最大价值
}

优化降维

#include<bits/stdc++.h>
using namespace std;

const int N=110;
int f[N];       //f[i]表示当前背包容量为i时的最大价值
int v[N][N],w[N][N],s[N];   //v[i][j]表示第i组物品中第j个物品的体积，w[i][j]表示第i组物品中第j个物品的价值，s[i]表示第i组物品的数量
int n,m,k;

int main(){
    cin>>n>>m;   //输入物品组数和背包容量
    for(int i=0;i<n;i++){
        cin>>s[i];      //输入当前物品组数的物品数量
        for(int j=0;j<s[i];j++){
            cin>>v[i][j]>>w[i][j];  //输入当前物品的体积和价值
        }
    }

    for(int i=0;i<n;i++){   //枚举物品组
        for(int j=m;j>=0;j--){  //枚举背包容量
            for(int k=0;k<s[i];k++){    //枚举当前物品组中的每一个物品
                if(j>=v[i][k])     f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);  //进行状态转移
            }
        }
    }
    cout<<f[m]<<endl;   //输出背包容量为m时的最大价值
}

二进制枚举优化

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 105;    // 最大物品种类数
const int MAXM = 100005; // 最大背包容量

int n, m;
int w[MAXN][MAXN], v[MAXN][MAXN]; // w[i][j] 表示第 i 种物品的第 j 个重量，v[i][j] 表示第 i 种物品的第 j 个价值
int f[MAXM]; // f[j] 表示背包容量为 j 时的最大价值

int main() {
    cin >> n >> m;  // 输入物品种类数和背包容量
    for(int i = 1; i <= n; i++) {
        int cnt;
        cin >> cnt;  // 输入第 i 种物品的数量
        w[i][0] = cnt;  // 记录第 i 种物品的数量
        for(int j = 1; j <= cnt; j++) {
            cin >> w[i][j] >> v[i][j];  // 输入第 i 种物品的第 j 个重量和价值
        }
    }

    for(int i = 1; i <= n; i++) {  // 遍历每种物品
        for(int j = m; j >= 0; j--) {  // 从大到小遍历每种背包容量
            for(int k = 0; k < (1 << w[i][0]); k++) {  // 枚举每种可能的选择情况，这里要用 w[i][0] 表示第 i 种物品的数量
                int ww = 0, vv = 0;  // 记录选中的物品的总重量和总价值
                for(int l = 1; l <= w[i][0]; l++) {  // 遍历第 i 种物品的所有物品
                    if((1 << (l - 1)) & k) {  // 如果第 l 个物品被选中
                        ww += w[i][l];  // 累加重量
                        vv += v[i][l];  // 累加价值
                    }
                }
                if(ww <= j) {  // 如果选中的物品总重量不超过背包容量 j
                    f[j] = max(f[j], f[j - ww] + vv);  // 更新背包容量为 j 时的最大价值
                }
            }
        }
    }

    cout << f[m] << endl;  // 输出背包容量为 m 时的最大价值，即为答案

    return 0;
}

三、线性DP

3.1概述

线性DP（Dynamic Programming）是指一种使用动态规划的方法解决问题的过程。通常来说，线性DP可以分为两种，即基于序列的线性DP和基于区间的线性DP。

基于序列的线性DP通常解决的是序列上的问题，如最长上升子序列（LIS）、最长公共子序列（LCS）等。这类问题的主要思路是定义状态，设计状态转移方程，以及求解最终结果。在设计状态转移方程时，需要考虑当前状态和之前状态之间的关系，以及如何根据之前的状态计算当前状态。在实现上，通常需要使用一维或二维数组来保存状态值。

基于区间的线性DP通常解决的是区间上的问题，如区间最大子段和、区间最小割等。这类问题的主要思路是定义状态，设计状态转移方程，以及求解最终结果。在设计状态转移方程时，需要考虑区间内的状态和区间之间的关系，以及如何根据区间内的状态计算区间之间的状态。在实现上，通常需要使用二维数组来保存状态值。

无论是基于序列的线性DP还是基于区间的线性DP，其思路都是相似的。需要注意的是，在实现时需要注意空间的使用，以及避免重复计算。此外，对于一些特殊的问题，还可以采用一些优化策略，如状态压缩、滚动数组、斜率优化等，从而提高算法的效率

3.2数字三角形

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5
输入格式

第一行包含整数 nn，表示数字三角形的层数。

接下来 nn 行，每行包含若干整数，其中第 ii 行表示数字三角形第 ii 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤5001≤n≤500,
−10000≤三角形中的整数≤10000−10000≤三角形中的整数≤10000

输入样例：
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
输出样例：
30

算法小课堂（四）动态规划

正序解法

#include <iostream>

using namespace std;

const int N = 510, INF = 1e9;
int f[N][N]; // f[i][j]表示到第i行第j列的最大路径和
int a[N][N]; // 存放输入的矩阵

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);

    // 初始化
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = -INF;
    f[1][1] = a[1][1];

    // 动态转移
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

    // 求解答案
    int max0 = -INF;
    for (int j = 1; j <= n; j++)
        max0 = max(max0, f[n][j]);

    cout << max0 << endl;
    return 0;
}

倒序解法

f(i,j)含义: 从最底层出发到第 i 行第 j 个数的最大路径和

每个点有两种选择: 向左上方走和向右上方走

对应的子问题为: f(i+1,j) 和 f(i+1,j+1)

倒序情况下不需要考虑边界条件

结果: f(1,1)

#include <iostream>

using namespace std;

const int N = 510;
int f[N][N];

int main()
{
    int n;
    cin >> n;

    // 读入三角形中的数值
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= i; j++)
            cin >> f[i][j];

    // 倒序 DP，从最后一行开始向上推
    for(int i = n; i >= 1; i--)
        for(int j = 1; j <= i; j++)
            f[i][j] += max(f[i+1][j], f[i+1][j+1]);

    cout << f[1][1] << endl;    // 输出最终的结果
    return 0;
}

二维优化为一维

#include <iostream>
using namespace std;
const int N = 510, INF = 1e9;

int f[N]; // f[j]表示到达当前行第j列的最大路径和
int a[N][N]; // 存放输入的矩阵

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);

    // 初始化
    for (int j = 1; j <= n; j++)
        f[j] = -INF;
    f[1] = a[1][1];

    // 动态转移
    for (int i = 2; i <= n; i++)
        for (int j = i; j >= 1; j--)
            f[j] = max(f[j], f[j - 1]) + a[i][j];

    // 求解答案
    int max0 = -INF;
    for (int j = 1; j <= n; j++)
        max0 = max(max0, f[j]);

    cout << max0 << endl;
    return 0;
}

记忆化搜索

#include <iostream>
using namespace std;

const int N = 510;

int n;
int d[N][N];
int f[N][N];

int dfs(int i, int j) {
    if (i == n) return d[i][j]; // 最底层

    if (f[i][j] != -1) return f[i][j]; // 记忆化

    int l = dfs(i + 1, j);
    int r = dfs(i + 1, j + 1);

    return f[i][j] = max(l, r) + d[i][j];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> d[i][j];
            f[i][j] = -1; // 初始化
        }
    }

    cout << dfs(1, 1) << endl;

    return 0;
}

3.3最长上升子序列

给定一个长度为 NN 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 NN。

第二行包含 NN 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤10001≤N≤1000，
−109≤数列中的数≤109−109≤数列中的数≤109

输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

算法小课堂（四）动态规划

朴素解法

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int w[N], f[N];

int main() {
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) cin >> w[i];

    // 动态规划求解最长上升子序列
    for (int i = 1; i <= n; i++) {
        f[i] = 1;    // 设f[i]默认为1，找不到前面数字小于自己的时候就为1
        for (int j = 1; j < i; j++) {
            if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1);    // 前一个小于自己的数结尾的最大上升子序列加上自己，即+1
        }
    }

    // 找出最大的 f[i] 值，即最长上升子序列的长度
    int mx = 0;
    for (int i = 1; i <= n; i++)
        mx = max(mx,f[i]);
    cout << mx << endl;
    return 0;
}

二分查找优化·

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int w[N], f[N];

// 在已经找到的上升子序列中二分查找第一个大于等于v的数的位置
int binary_search(int l, int r, int v) {
    while (l < r) {
        int mid = l + r >> 1;
        if (f[mid] < v) l = mid + 1;
        else r = mid;
    }
    return l;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);

    int len = 1;   // LIS的长度，初始化为1，即只有第一个数自己本身是一个上升子序列
    f[1] = w[1];   // 第一个上升子序列就是第一个数自己本身
    for (int i = 2; i <= n; i++) {    // 从第二个数开始计算
        if (w[i] > f[len]) {    // 如果当前的数比已经找到的上升子序列中最后一个数还大，那么直接加入上升子序列中
            f[++len] = w[i];
        } else {   // 否则，在已经找到的上升子序列中找到第一个大于等于当前数的位置，将其加入上升子序列中
            int pos = binary_search(1, len, w[i]);
            f[pos] = w[i];
        }
    }
    printf("%d\n", len);    // 输出最长上升子序列的长度

    return 0;
}

回溯路径

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int w[N], f[N], g[N];

int main() {
    // 输入数据
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        cin >> w[i];

    // 动态规划求解最长上升子序列
    for (int i = 1; i <= n; i++) {
        f[i] = 1;    // 设f[i]默认为1，找不到前面数字小于自己的时候就为1
        g[i] = 0;    // 记录转移的来源，初始化为0
        for (int j = 1; j < i; j++) {
            if (w[i] > w[j]) // 如果i位置的数字比j位置的大
                if (f[i] < f[j] + 1) {  // 如果j位置到i位置的数字可以构成更长的子序列
                    f[i] = f[j] + 1;  // 更新f[i]的值
                    g[i] = j;   // 记录i位置的最优来源
                }
        }
    }

    // 找出最大的 f[i] 值，即最长上升子序列的长度
    int k = 1;
    for (int i = 1; i <= n; i++)
        if (f[k] < f[i])
            k = i;
    printf("%d\n", f[k]);

    // 输出最长上升子序列
    int res[N], len = 0;
    while (k) {
        res[++len] = w[k];
        k = g[k];
    }
    for (int i = len; i >= 1; i--)
        printf("%d ", res[i]);

    return 0;
}

记忆化搜索

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int seq[MAXN];  // 存储输入的数字序列
int memo[MAXN]; // memo数组用于记忆化搜索，存储已经计算过的子问题的答案
int n;          // 数字序列的长度

// dfs函数表示以第i个数字为开头的最长上升子序列的长度
int dfs(int i) {
    if (memo[i] != -1) return memo[i];  // 如果已经计算过这个子问题的答案，则直接返回答案
    int res = 1;                        // 初始化答案为1，表示最长上升子序列的长度至少为1
    for (int j = i+1; j < n; j++) {     // 枚举所有可能的下一个数字
        if (seq[j] > seq[i]) {          // 如果这个数字比当前数字大，则可以将它添加到当前上升子序列中
            res = max(res, dfs(j) + 1); // 递归求解以它为开头的最长上升子序列的长度，再加上当前数字，得到当前上升子序列的长度
        }
    }
    memo[i] = res;                      // 将当前子问题的答案保存到memo数组中，以便下次计算时直接返回答案
    return memo[i];
}

int main() {
    memset(memo, -1, sizeof(memo));    // 初始化memo数组为-1，表示所有子问题的答案都还没有计算过
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> seq[i];                 // 输入数字序列
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dfs(i));        // 对于每一个数字，求解以它为开头的最长上升子序列的长度，并更新答案
    }
    cout << ans << endl;               // 输出最长上升子序列的长度
    return 0;
}

3.4 最长公共子序列

最长公共子序列（Longest Common Subsequence，LCS）是指在给定两个序列中，找到一个最长的子序列，使得该子序列在两个序列中均出现。

例如，对于序列 "ABCD" 和 "BDCA"，它们的最长公共子序列是 "BD"，长度为 2

最长公共子序列可以使用多种算法来解决，其中比较常见的算法包括：

动态规划：上面已经给出了动态规划的解法，时间复杂度为 O(n^2)，空间复杂度也为 O(n^2)。

递归：可以将问题递归地划分为子问题，递归求解。时间复杂度为指数级别，不太实用，但可以作为理解动态规划的一种方法。

滑动窗口：可以将最长公共子序列转化为最长连续子序列，使用滑动窗口来求解。时间复杂度为 O(n)，空间复杂度为 O(1)。

给定两个长度分别为 N和 M 的字符串 A 和 B，求既是 A 的子序列又是B 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 N 和 M。

第二行包含一个长度为 N 的字符串，表示字符串 A。

第三行包含一个长度为 M 的字符串，表示字符串 B。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N,M≤1000

输入样例：
4 5
acbd
abedc
输出样例：
3

算法小课堂（四）动态规划

实验书模板

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
char A[N], B[N];
int from[N][N]; //记录LCS构造路径
int dp[N][N]; //记录LCS长度
int n, m;

void LCSLength(int n, int m) {
    //初始化
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 0; //第一列初始化为0
    }

    for (int i = 1; i <= m; i++) {
        dp[0][i] = 0; //第一行初始化为0
    }

    //递推求解
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i] == B[j]) { //字符匹配，LCS长度+1
                dp[i][j] = dp[i - 1][j - 1] + 1;
                from[i][j] = 1; //记录路径为“左上角”
            } else if (dp[i - 1][j] >= dp[i][j - 1]) { //选择左边的值
                dp[i][j] = dp[i - 1][j];
                from[i][j] = 2; //记录路径为“上边”
            } else { //选择上面的值
                dp[i][j] = dp[i][j - 1];
                from[i][j] = 3; //记录路径为“左边”
            }
        }
    }
}

//LCS构造
void LCS(int i, int j) {
    if (i == 0 || j == 0) return; //递归终止条件

    if (from[i][j] == 1) { //当前字符匹配，输出后递归“左上角”
        LCS(i - 1, j - 1);
        cout << A[i]; //输出当前字符
    } else if (from[i][j] == 2) { //选择上面的值，递归“上边”
        LCS(i - 1, j);
    } else { //选择左边的值，递归“左边”
        LCS(i, j - 1);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    scanf("%s %s", A + 1, B + 1);
    LCSLength(n, m);
    cout << dp[n][m] << endl; //输出LCS长度
    LCS(n, m);
    return 0;
}

朴素解法

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N]; // f[i][j] 表示 a 的前 i 个字符和 b 的前 j 个字符的最长公共子序列长度
int main() {
  cin >> n >> m >> a + 1 >> b + 1; // 输入 n、m 和字符串 a、b，注意要从下标 1 开始读入
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (a[i] == b[j]) { // 如果当前字符相同，则最长公共子序列长度加一
        f[i][j] = f[i - 1][j - 1] + 1;
      } else { // 如果当前字符不同，则最长公共子序列长度为 a 的前 i-1 个字符和 b 的前 j 个字符的最长公共子序列长度，或者是 a 的前 i 个字符和 b 的前 j-1 个字符的最长公共子序列长度中的较大值
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);
      }
    }
  }
  cout << f[n][m] << '\n'; // 输出最长公共子序列长度
  return 0;
}

记忆化搜索递归解法

具体步骤如下：

定义一个记忆数组 memo，其中 memo[i][j] 表示字符串 a 的前 i 个字符和字符串 b 的前 j 个字符的最长公共子序列长度。

对于每个位置 (i, j)，如果 a[i] == b[j]，则最长公共子序列长度加一，否则最长公共子序列长度为 a 的前 i-1 个字符和 b 的前 j 个字符的最长公共子序列长度，或者是 a 的前 i 个字符和 b 的前 j-1 个字符的最长公共子序列长度中的较大值。

递归计算 memo[i][j]，如果 memo[i][j] 已经计算过，则直接返回 memo[i][j]。

计算 memo[n][m]，其中 n 和 m 分别表示字符串 a 和 b 的长度。

返回 memo[n][m]。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int memo[N][N]; // 定义记忆数组
int dfs(int i, int j) {
    if (i == 0 || j == 0) return 0; // 边界情况
    if (memo[i][j] != -1) return memo[i][j]; // 如果 memo[i][j] 已经计算过，则直接返回 memo[i][j]
    if (a[i] == b[j]) memo[i][j] = dfs(i - 1, j - 1) + 1; // 如果 a[i] == b[j]，则最长公共子序列长度加一
    else memo[i][j] = max(dfs(i - 1, j), dfs(i, j - 1)); // 否则最长公共子序列长度为 a 的前 i-1 个字符和 b 的前 j 个字符的最长公共子序列长度，或者是 a 的前 i 个字符和 b 的前 j-1 个字符的最长公共子序列长度中的较大值
    return memo[i][j];
}
int main() {
    cin >> n >> m >> a + 1 >> b + 1;
    memset(memo, -1, sizeof memo); // 初始化记忆数组
    int ans = dfs(n, m);
    cout << ans << '\n'; // 输出最长公共子序列长度
    return 0;
}

四、区间DP

4.1概述

区间DP是动态规划算法中的一种常见形式，它通常用于解决区间问题，例如最长回文子序列、石子合并，区间最大子段和等问题。

区间DP的基本思想是将原问题划分成若干子问题，然后通过计算子问题的最优解来推导出原问题的最优解。通常情况下，一个区间问题的最优解可以通过其子区间的最优解来求解。

区间DP的状态转移方程通常具有以下形式：

其中 $dp_{i,j}$ 表示原问题中区间 $[i,j]$ 的最优解，$k$ 表示将区间 $[i,j]$ 划分成两个子区间 $[i,k]$ 和 $[k+1,j]$，$cost(i,j,k)$ 表示将区间 $[i,j]$ 划分成子区间 $[i,k]$ 和 $[k+1,j]$ 的代价。

在实际应用中，通常需要根据具体问题来设计状态转移方程

4.2石子合并

设有 N 堆石子排成一排，其编号为 1,2,3,…,N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 44 堆石子分别为 1 3 5 2，我们可以先合并 1、2堆，代价为 4，得到 4 5 2，又合并 1、2堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=244+9+11=24；

如果第二步是先合并 2、3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=224+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式

第一行一个数 N表示石子的堆数 N。

第二行 N 个数，表示每堆石子的质量(均不超过 1000)。

输出格式

输出一个整数，表示最小代价。

数据范围

1≤N≤300

输入样例：
4
1 3 5 2
输出样例：
22

算法小课堂（四）动态规划

朴素解法

#include <iostream>
#include <cstring>
using namespace std;

const int N = 310;
int n;
int s[N]; // 前缀和数组
int f[N][N]; // 动态规划状态数组

int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> s[i];
        s[i] += s[i - 1]; // 计算前缀和
    }

    for (int len = 2;len <= n;len++) { // 枚举区间长度
        for (int i = 1;i + len - 1 <= n;i++) { // 枚举区间左端点
            int l = i,r = i + len - 1; // 区间右端点
            f[l][r] = 1e9; // 初始化为极大值
            for (int k = l;k <= r - 1;k++) { // 枚举区间分割点
                f[l][r] = min (f[l][r],f[l][k] + f[k + 1][r] + s[r] - s[l - 1]); // 状态转移方程
            }
        }
    }

    cout << f[1][n] << endl; // 输出最终结果
    return 0;
}

记忆化搜索

#include <iostream>
#include <cstring>
using namespace std;

const int N = 310;
int n;
int s[N]; // 前缀和数组
int f[N][N]; // 动态规划状态数组

// 记忆化搜索函数
int dfs (int l,int r) {
    if (f[l][r] != -1) return f[l][r]; // 已经计算过，直接返回
    if (l == r) return 0; // 只有一个石子，不需要合并

    int res = 1e9;
    for (int k = l;k < r;k++) { // 枚举分割点
        res = min (res,dfs (l,k) + dfs (k + 1,r) + s[r] - s[l - 1]); // 更新最小代价
    }
    return f[l][r] = res; // 记录并返回结果
}

int main () {
    cin >> n;
    memset (f,-1,sizeof (f)); // 初始化为 -1
    for (int i = 1;i <= n;i++) {
        cin >> s[i];
        s[i] += s[i - 1]; // 计算前缀和
    }

    cout << dfs (1,n) << endl; // 输出最终结果
    return 0;
}

4.3最大子段和

最大子段和问题是一个经典的算法问题，指的是在一个数列中，找到一个子段（可以为空），使得该子段内所有数的和最大。例如( -2,11,-4,13,-5,-2 )最大子段是{ 11,-4,13 }其和为20。

朴素算法

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5+10;
int n;
int a[N];
int f[N]; // f[i]表示以i结尾的最大子段和

int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }

    f[1] = a[1];
    int ans = f[1];
    for (int i = 2;i <= n;i++) {
        f[i] = max (f[i-1]+a[i],a[i]); // 状态转移方程
        ans = max (ans,f[i]); // 更新最大子段和
    }

    cout << ans << endl;
    return 0;
}

记忆化搜索

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5+10;
int n;
int a[N];
int memo[N];

// 递归计算以位置i结尾的最大子段和
int dp(int i) {
    // 如果i=1，则以位置1结尾的最大子段和就是a[1]
    if (i == 1) return memo[1] = a[1];
    // 如果memo[i]已经被计算过，则直接返回memo[i]
    if (memo[i]) return memo[i];
    // 如果dp(i-1)>0，则以位置i结尾的最大子段和就是dp(i-1)+a[i]
    if (dp(i-1) > 0) return memo[i] = dp(i-1) + a[i];
    // 否则以位置i结尾的最大子段和就是a[i]
    return memo[i] = a[i];
}

int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    int res = a[1];
    // 枚举所有的i，取它们的最大值作为最终答案
    for (int i = 1;i <= n;i++) res = max(res, dp(i));
    cout << res << endl;
    return 0;
}

递归分治

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e5+10;
int n;
int a[N];

// 求跨越中点的最大子段和
int cross(int l, int r, int mid) {
    int sum = 0, lmax = a[mid], rmax = a[mid+1];
    for (int i = mid;i >= l;i--) {
        sum += a[i];
        lmax = max(lmax, sum);
    }
    sum = 0;
    for (int i = mid+1;i <= r;i++) {
        sum += a[i];
        rmax = max(rmax, sum);
    }
    return lmax + rmax;
}

// 递归求解最大子段和
int maxSub(int l, int r) {
    if (l == r) return a[l];
    int mid = l + r >> 1;
    int lmax = maxSub(l, mid);
    int rmax = maxSub(mid+1, r);
    int cmax = cross(l, r, mid);
    return max({lmax, rmax, cmax});
}

int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    cout << maxSub(1, n) << endl;
    return 0;
}

贪心算法

#include <iostream>
using namespace std;

const int N = 1e5+10;
int n;
int a[N];

int main () {
    // 输入数据
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    // 贪心求解最大子段和
    int sum = 0, res = a[1];
    for (int i = 1;i <= n;i++) {
        if (sum < 0) sum = a[i];
        else sum += a[i];
        res = max(res, sum);
    }
    // 输出结果
    cout << res << endl;
    return 0;
}

4.3进阶林大OJ 1443环形最大子段和

Description

给出长度是N的数组，N个数围成一个环形，求最大子段和

Input

多组输入
第一行：输入N，为数组的长度(2=<N<=50000)
第二行：N个值，表示数组中元素的值(10^9<=a[i]<=10^9)

Output

输出最大子段和

Sample Input

5
1 -1 -1 -1 5

Sample Output

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 5e4+10;
int n;
int a[N];
int f[N], g[N]; // f[i]表示以i结尾的最大子段和，g[i]表示以i结尾的最小子段和

int main () {
    while (cin >> n) {
        int sum = 0;
        for (int i = 1;i <= n;i++) {
            cin >> a[i];
            sum += a[i];
        }

        // 最大子段和
        f[1] = a[1];
        int ans1 = f[1];
        for (int i = 2;i < n;i++) {
            f[i] = max (f[i-1]+a[i],a[i]);
            ans1 = max (ans1,f[i]);
        }
        ans1 = max (ans1, f[n] = max(f[n-1]+a[n], a[n])); // 计算以n结尾的最大子段和

        // 最小子段和
        g[1] = a[1];
        int ans2 = g[1];
        for (int i = 2;i < n;i++) {
            g[i] = min (g[i-1]+a[i],a[i]);
            ans2 = min (ans2,g[i]);
        }
        ans2 = min (ans2, g[n] = min(g[n-1]+a[n], a[n])); // 计算以n结尾的最小子段和

        int ans = max(ans1, sum-ans2); // 计算最终答案
        cout << ans << endl;
    }
    return 0;
}

4.4最长回文子序列

最长回文子序列问题是一个经典的字符串问题，给定一个字符串S，找到其中最长的回文子序列。

回文是指正序和倒序相同的字符串，而子序列是从原字符串中删除一些字符（可以不删除）后得到的新字符串，其中字符的相对顺序保持不变。

例如，字符串S = “bbbab”，它的最长回文子序列是“bbbb”，长度为4;字符串S = “cbbd”，它的最长回文子序列是“bb”，长度为2。

代码中用一个一维数组'dp

为了避免使用两个变量来表示子串的左右端点，代码中使用了双重循环进行枚举，其中外层循环枚举子串的右端点j，内层循环枚举子串的左端点i。这样，子串的长度就可以表示为j-i+1。

对于每个子问题，我们有三种情况：

当子串长度为1时，只包含一个字符，是回文串，此时dp[j]的值应为1。

当子串的左右端点的字符相等时，该子串的最长回文子序列长度为dp[j-1]的值加上2，因为子串两端的字符相等，所以回文子序列的长度加2。

当子串的左右端点的字符不相等时，最长回文子序列的长度可能在子串的左半部分，也可能在右半部分，因此需要从dp[j-1]和dp[j]中取最大值作为dp[j]的值。

在计算dp[j]的值之前，我们需要将上一轮的dp[j]的值保存下来，因为后续计算dp[j]时需要用到上一轮的结果，这样可以避免之前计算得到的结果被覆盖的问题。

最后输出dp[n-1]的值即为给定字符串的最长回文子序列的长度。

朴素解法

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010; // 定义常量N为1010，表示最大字符串长度

int dp[N]; // 定义长度为N的数组dp，用于保存子问题的解

int main()
{
    string s; // 定义字符串s，用于保存输入的字符串
    cin >> s; // 读入字符串s

    int n = s.size(); // 计算字符串s的长度，将其保存到变量n中

    dp[0] = 0; // 初始化dp[0]为0

    for (int i = n - 1; i >= 0; i--) { // 枚举i从n-1到0，倒序枚举
        int pre = 0; // 记录上一轮dp[j-1]的值，初始化为0
        for (int j = i; j < n; j++) { // 枚举j从i到n，正序枚举
            int temp = dp[j]; // 记录上一轮dp[j]的值
            if (i == j) { // 特殊情况，i==j，子串长度为1
                dp[j] = 1; // 单个字符是回文串
            } else if (s[i] == s[j]) { // 字符s[i]和s[j]相等
                dp[j] = pre + 2; // 状态转移方程，dp[j]更新为dp[j-1]的值加上2
            } else { // s[i]和s[j]不相等
                dp[j] = max(dp[j - 1], dp[j]); // 状态转移方程，dp[j]更新为dp[j-1]和dp[j]中的最大值
            }
            pre = temp; // 更新pre为上一轮dp[j]的值
        }
    }

    cout << dp[n - 1] << endl; // 输出dp[n-1]，即最长回文子序列的长度

    return 0;
}

记忆化搜索

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

int n;
int f[N][N]; // 用f[i][j]保存字符串s[i...j]的最长回文子序列的长度
string s;

int dfs(int i, int j)
{
    if (i > j) return 0; // 子串为空，最长回文子序列长度为0
    if (i == j) return 1; // 子串只包含一个字符，是回文串，最长回文子序列长度为1
    if (f[i][j] != -1) return f[i][j]; // 如果当前子问题已经求解过，直接返回

    int res = 0;
    if (s[i] == s[j]) // 如果左右端点的字符相等，则包含左右端点的最长回文子序列长度加2
        res = dfs(i+1, j-1) + 2;
    else // 如果左右端点的字符不相等，则可能在左半部分或右半部分，取最大值即可
        res = max(dfs(i+1, j), dfs(i, j-1));

    return f[i][j] = res; // 将当前子问题的解保存到数组中
}

int main()
{
    cin >> s;
    n = s.size();

    memset(f, -1, sizeof f); // 初始化数组f

    cout << dfs(0, n-1) << endl; // 求解最长回文子序列的长度

    return 0;
}

五、计数类DP

5.1 整数划分

整数划分是指将一个正整数n拆分成若干个正整数的和的不同方案数。例如，正整数4可以拆分成1+1+1+1、1+1+2、1+3、2+2、4这5种方案，因此它的整数划分数为5。

一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。

我们将这样的一种表示称为正整数 n 的一种划分。

现在给定一个正整数 n，请你求出n 共有多少种不同的划分方法。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 109+7取模。

数据范围

1≤n≤1000

输入样例:
5
输出样例：
7

朴素解法

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N][N];

int main()
{
    cin >> n;

    for(int i = 0;i <= n;i++) f[i][0] = 1;

    for (int i = 1; i <= n; i ++ )
        for(int j = 0; j <= n; j ++ ){
            f[i][j] = f[i-1][j]; // j < i ,一个i都放不下的情况
            // j >= i的情况
            if(j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
        }

    cout << f[n][n] << endl;

    return 0;

}

优化成一维

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7; // 定义常量N为1010，mod为10^9 + 7

int n;
int f[N]; // 定义长度为N的数组f

int main()
{
    cin >> n; // 输入n

    f[0] = 1; // 初始化f[0]为1

    for (int i = 1; i <= n; i ++ ) // 枚举i从1到n
        for(int j = i; j <= n; j ++ ){ // 枚举j从i到n
            f[j] = (f[j] + f[j - i]) % mod; // 状态转移方程
        }

    cout << f[n] << endl; // 输出f[n]

    return 0;
}

分治解法

对于整数划分问题，我们可以将将n划分成若干个数的和的方案数分解为两个子问题：

将n-m划分成若干个数的和的方案数，其中最小的数为m；

将n划分成若干个数的和的方案数，其中最小的数不小于m+1。

其中，第一个子问题中最小的数为m，所以只需要将n-m划分成若干个数的和，最小的数为m，即可得到将n划分成若干个数的和中最小的数为m的方案数。第二个子问题中最小的数不小于m+1，因此只需要将n划分成若干个数的和，最小的数不小于m+1，即可得到将n划分成若干个数的和中最小的数不为m的方案数。

最后，将两个子问题的解加起来即可得到将n划分成若干个数的和的方案数。

由于每次将n减小，所以在计算过程中需要递归处理，直到n=0为止，此时只有一种划分方式，即n=0。因此，这个递归过程可以看作是一个将大问题分解成若干个小问题，对每个小问题分别求解，最终将小问题的解合并起来得到大问题的解的过程，符合分治算法的思想

#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;

int countPartition(int n, int m) {
    if (n == 0) {
        return 1;
    }
    if (m == 0) {
        return 0;
    }
    int count = 0;
    if (n >= m) {
        count = countPartition(n - m, m);
    }
    count = (count + countPartition(n, m - 1)) % MOD;
    return count;
}

int main() {
    int n;
    cin >> n;
    int count = countPartition(n, n);
    cout << count << endl;
    return 0;
}

记忆化搜索

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];  // 存储记忆化搜索的结果，f[i][j]表示将正整数i划分成若干个正整数之和，其中每个正整数不超过j的划分方案数。

// 定义一个函数dp(i,j)表示将正整数i划分成若干个正整数之和，其中每个正整数不超过j的划分方案数。
int dfs(int i, int j)
{
    // 当i为0时，说明剩余的部分已经划分完毕，只有一种划分方案，即不再划分。
    if (i == 0) return 1;
    // 如果f[i][j]已经计算过了，就直接返回它的值。
    if (f[i][j] != -1) return f[i][j];
    int res = 0;
    // 对于每个小于等于j和i的正整数k，将n-k递归地划分成若干个正整数之和，并将这些子问题的解相加，即可得到dp(i,j)的值。
    for (int k = 1; k <= j && k <= i; k++)
        res = (res + dfs(i - k, k)) % mod;
    // 将计算结果存储到f[i][j]中，并返回它的值。
    return f[i][j] = res;
}

int main()
{
    cin >> n;
    memset(f, -1, sizeof f); // 初始化f数组
    cout << dfs(n, n) << endl; // 输出答案
    return 0;
}

六、记忆化搜索

6.1滑雪

给定一个 RR 行 CC 列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 ii 行第 jj 列的点表示滑雪场的第 ii 行第 jj 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：
 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9
在给定矩阵中，一条可行的滑行轨迹为 24−17−2−124−17−2−1。

在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−125−24−23−…−3−2−1，沿途共经过 2525 个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数 RR 和 CC。

接下来 RR 行，每行包含 CC 个整数，表示完整的二维矩阵。

输出格式

输出一个整数，表示可完成的最长滑雪长度。

数据范围

1≤R,C≤3001≤R,C≤300,
0≤矩阵中整数≤100000≤矩阵中整数≤10000

输入样例：
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
输出样例：
25

算法小课堂（四）动态规划

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int n,m; //网格滑雪场的行和列
int f[N][N]; //状态转移式
int h[N][N]; //网格滑雪场
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int dp(int x,int y){
    int &v = f[x][y]; //Y总说的小技巧，等于把f[x][y]简化成了v，如果v发生变化，f[x][y]也会随之变化
    if(v != -1) return v; //如果已经计算过了，就可以直接返回答案
    v = 1; //注意v要先赋值为1哦~
    for(int i = 0;i < 4;i ++){ //四个方向
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && h[x][y] > h[xx][yy]){ //判断这点是否能走
            v = max(v,dp(xx,yy) + 1); //更新
        }
    }
    return v; //别忘了返回v啊（被坑了
}
int main(){
    cin>>n>>m; //输入滑雪场行和列
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cin>>h[i][j]; //读入滑雪场数据
        }
    }
    memset(f,-1,sizeof f);
    int res = 0; //最后答案
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            //因为这个人可以在任意一点开始滑，所以要遍历一遍滑雪场
            res = max(res,dp(i,j)); //更新答案
        }
    }
    cout<<res<<endl;
    return 0;
}

七、DP优化

7.1矩阵连乘

算法小课堂（四）动态规划

备忘录方法

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int n,m;
int dp[N][N],s[N][N];	// s[l][r] 记录[l,r]最优分割点
int p[N];

//备忘录
int LookupChain(int l, int r) {
    if (dp[l][r] > 0) return dp[l][r];	//查表
    if (l == r) return 0;

    int u = LookupChain(l, l) + LookupChain(l + 1, r) + p[l - 1] * p[l] * p[r];
    s[l][r] = l;

    for (int k = l + 1; k < r; k++) {
        int t = LookupChain(l, k) + LookupChain(k + 1, r) + p[l - 1] * p[k] * p[r];
        if (t < u) {
            u = t;
            s[l][r] = k;
        }
    }
    return dp[l][r] = u;	//更新备忘录
}

//回溯输出方案
void TraceBack(int l,int r) {
    if (l == r) return ;
    int k = s[l][r];	//[l,r] 区间最优分割点 k
    TraceBack(l, k);
    TraceBack(k + 1, r);
    cout << "Multiply A" << l << "," << k
         << "and A" << k + 1 << "," << r << endl;
}

int main() {
    cin >> n;
    for(int i = 0; i <=n; ++i) {
        cin >> p[i];
    }

    memset(dp,0,sizeof dp);		//清空 dp
    memset(s,0,sizeof s);		//清空 s

    cout << "LookupChain: " << LookupChain(1, n) << endl;
    cout << endl;
    TraceBack(1, n);
    cout << endl;
    return 0;
}

备忘录解法通常使用一个数组来记录已经求解过的结果，数组中的元素起到缓存的作用，保存之前计算的结果，避免在后续的计算中重复计算。

在递归算法中，如果当前需要计算的结果已经被保存在数组中，则直接返回已经计算过的结果，否则继续递归计算，并将结果保存在数组中，以便后续使用。

记忆化搜索

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 105;
const int INF = 1e9;
int n;
int a[MAXN], dp[MAXN][MAXN]; // dp[i][j]表示从第i个矩阵到第j个矩阵所需的最小乘法次数

int solve(int i, int j) {
    if (dp[i][j] != -1) return dp[i][j]; // 如果已经计算过了，则直接返回之前的结果
    if (i == j) return 0; // 如果只有一个矩阵，则不需要计算，直接返回0
    dp[i][j] = INF; // 先将dp[i][j]初始化为无穷大
    for (int k = i; k < j; k++) {
        dp[i][j] = min(dp[i][j], solve(i, k) + solve(k + 1, j) + a[i - 1] * a[k] * a[j]); // 根据状态转移方程计算dp[i][j]
    }
    return dp[i][j]; // 返回dp[i][j]
}

int main() {
    memset(dp, -1, sizeof(dp)); // 初始化dp数组为-1
    cin >> n;
    for (int i = 0; i <= n; i++) cin >> a[i]; // 输入矩阵的行和列的数值
    cout << solve(1, n) << endl; // 输出从第一个矩阵到第n个矩阵所需的最小乘法次数
    return 0;
}

记忆化搜索与备忘录区别

记忆化搜索是自顶向下的递归，它通过递归调用实现对问题的分解，并将分解出的子问题的答案保存在一个数组中。在递归时，先判断当前问题是否已经计算过，如果已经计算过，则直接返回之前的结果，否则，继续递归求解子问题，最终得到答案。因为是自顶向下递归，所以会存在重复计算的问题，但通过使用数组保存结果，可以避免重复计算。

备忘录则是自底向上的迭代，它通过迭代求解子问题并将子问题的答案保存在一个数组中。在求解子问题时，先判断当前问题是否已经计算过，如果已经计算过，则直接返回之前的结果，否则，计算并保存当前问题的结果。由于是自底向上迭代，所以不存在重复计算的问题，同时，备忘录可以避免递归树过深造成的栈溢出问题。文章来源地址https://www.toymoban.com/news/detail-427095.html

朴素解法

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 100;  // 定义最大矩阵数量为100
const int INF = 0x3f3f3f3f;  // 定义正无穷

// 矩阵链乘法动态规划求解函数，输入矩阵规模p和矩阵数量n，返回最小乘法次数
int matrixChainOrder(int p[], int n) {
    int f[MAX_SIZE][MAX_SIZE];  // 定义状态矩阵
    for (int i = 1; i <= n; i++) {  // 初始化对角线为0
        f[i][i] = 0;
    }

    // L是区间长度，从2开始枚举
    for (int L = 2; L <= n; L++) {
        // i是区间左端点，最右端点为n-L+1
        for (int i = 1; i <= n - L + 1; i++) {
            int j = i + L - 1;  // 区间右端点为i+L-1
            f[i][j] = INF;  // 初始化为正无穷

            // k为分割点，从i到j-1枚举
            for (int k = i; k < j; k++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + p[i-1]*p[k]*p[j]); // 根据状态转移方程求解
            }
        }
    }

    return f[1][n];  // 返回从第一个矩阵乘到最后一个矩阵的最小乘法次数
}

int main() {
    int n, p[MAX_SIZE];  // n为矩阵数量，p为矩阵规模数组
    cin >> n;  // 输入矩阵数量
    for (int i = 0; i <= n; i++) {
        cin>>p[i];  // 输入矩阵规模
    }
    cout<< matrixChainOrder(p, n) << endl;  // 输出最小乘法次数
    return 0;
}

到了这里，关于算法小课堂（四）动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

算法小课堂（四）动态规划

一、概况

二、背包

2.0闫式dp分析法

2.1 0-1背包

朴素解法

滚动数组

2.2 完全背包

朴素解法

优化降维

滚动数组

2.3完全背包和0-1背包的区别与联系

2.4多重背包问题

朴素解法

二进制枚举优化

贪心算法

单调队列优化

2.5分组背包问题

朴素算法

优化降维

二进制枚举优化

三、线性DP

3.1概述

3.2数字三角形

正序解法

倒序解法

二维优化为一维

记忆化搜索

3.3最长上升子序列

朴素解法

二分查找优化·

回溯路径

记忆化搜索

3.4 最长公共子序列

实验书模板

朴素解法

记忆化搜索递归解法

四、区间DP

4.1概述

4.2石子合并

朴素解法

记忆化搜索

4.3最大子段和

朴素算法

记忆化搜索

递归分治

贪心算法

4.3进阶林大OJ 1443环形最大子段和

4.4最长回文子序列

朴素解法

记忆化搜索

五、计数类DP

5.1 整数划分

朴素解法

优化成一维

分治解法

记忆化搜索

六、记忆化搜索

6.1滑雪

七、DP优化

7.1矩阵连乘

备忘录方法

记忆化搜索

记忆化搜索与备忘录区别

朴素解法

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2