动态规划-线性DP问题总结（一）

什么是动态规划

动态规划通过额外的空间将已经搜索过的相似的结果（指某些具有相同性质解的集合）用一个数组存起来，所以DP中的状态转移看上去是某两三个值之间的推导，其实是某两三个集合之间的状态转移！

常见的线性DP问题

1. 最长上升子序列
2. 最长公共子序列
3. 最短编辑距离
4. 数字三角形

最长上升子序列

典型题例：

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

示例 ：

输入：第一行包含整数 N。
      第二行包含 N 个整数，表示完整序列。品的体积和价值
7
3 1 2 1 8 5 6
输出：
4

思路
状态表示：集合f[i]表示以第i个数结尾的上升子序列的集合；属性：为集合中max

状态计算：第i的数固定，则以集合第i-1为哪个数进行集合划分，（0 ~ i-1）
f[i] = max(f[j] + 1), 条件：a[j] < a[j],j = 0,1,3,...i-1;

时间复杂都计算：状态数量状态转移的数量–> nn 为O(n^2)

代码：

#include 
#include 

using namespace std;

const int N = 1010;

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

int main() {
    
    cin >> n;
    for (int i = 1; i <= n; i ++) scanf("%d",&a[i]);
    
    for (int i = 1; i <= n; i ++) {
        f[i] = 1;  //只有a[i]
        for (int j = 1; j < i; j ++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i ++) res = max(res, f[i]);
    printf("%d\n", res);
    
    return 0;
}

最长公共子序列

典型题例：

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

输入：第一行包含两个整数 N 和 M。
      第二行包含一个长度为 N 的字符串，表示字符串 A。
      第三行包含一个长度为 M 的字符串，表示字符串 B。
      字符串均由小写字母构成。
4 5
acbd
abedc
输出：
3

思路
状态表示：集合f[i,j]：所有A[1_i]与b[1j]的公共子序列的集合；属性：max

状态计算：在f[i-1,j-1], f[i-1,j], f[i,j-1], f[i-1,j-1]+1 四个集合中的最大值
因为f[i-1,j], f[i,j-1]已经包含f[i-1,j-1];所以只需要比较三个集合的最大值即可

代码：

#include 
#include 

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];

int f[N][N];

int main() {
    
    cin >> n >> m >> a + 1 >> b + 1;  //
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);  //
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
        
    cout << f[n][m] << endl;
    
    return 0;
}

传送门：动态规划- 背包问题总结（二）

充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习