C++ ---- 线性DP三道入门必会例题_dp入门思路 c++

一、最长上升子序列。

题目描述

给出一个由 n(n≤5000)个不超过 10^6 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 n，表示序列长度。

第二行有 n 个整数，表示这个序列。

输出格式

一个整数表示答案。

输入输出样例

输入 #1复制

6
1 2 4 1 3 4

输出 #1复制

4

解题思路：设一个dp数组，dp[i]表示从开头到第i个数最长上升子序列的长度；i指针遍历从第1个数到第n个，j指针遍历在i之前的所有数字，如果a[i] > a[j]，就表示序列上升，所以dp[i] = max(dp[i], dp[j] + 1)

注意：很多人这里会写dp[i] = dp[j] + 1，这是错误写法，因为在遍历i之前的所有数字时，可能有多条上升子序列可以加入a[i]这个数，但是这些序列长度不一样，可能有的长有的短，因此max函数用于筛选前面已知上升子序列的长度。

代码实现：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n, a[N], dp[N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (a[j] < a[i])dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int res = -2e9;
    for (int i = 1; i <= n; i++)res = max(res, dp[i]);
    cout << res << endl;
    return 0;
}

二、最长公共子序列。

给定两个字符串text1和text2，返回它们最长的公共子序列的长度。

字符串的子序列是从原始字符串生成的新字符串，其中删除了一些字符（可以是一个字符），而不会更改其余字符的相对顺序。 （例如，“ ace”是“ abcde”的子序列，而“ aec”则不是）。 两个字符串的公共子序列是两个字符串共有的子序列。

如果没有公共子序列，则返回0。

测试样例：

4 5
acbd
abcde

结果：

3

解题思路：设f[i][j]表示text1的位置i和text2的位置j之前的最长公共子序列；这里无非三种情况：

1.i < j----此时f[i][j] = f[i - 1][j]

2.i > j----此时f[i][j] = f[i][j - 1]

3.i = j----此时f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1)

代码实现：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 110;
int n, m, dp[N][N];
char a[N], b[N];
int main()
{
	cin >> n >> m;
	cin >> a + 1 >> b + 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			if (a[i] == b[j])dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
		}
	}
	cout << dp[n][m] << endl;
	return 0;
}

三、数字三角形。

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

输入格式

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

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

输出格式

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

数据范围

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

解题思路：

典型的“走迷宫”式DP， 由题意得，他只有两种走法：（1）从左上下来（2）从上方下来。

所以设dp[i][j]表示走到(i, j)这个地方时权值和，代码实现如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 110;
int dp[N][N], a[N][N], n, res = -2e9;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			cin >> a[i][j];
		}
	}
	for (int i = 0; i <= n; i++)//初始化操作
	{
		for (int j = 0; j <= i; j++)
		{
			dp[i][j] = -2e9;
		}
	}
	dp[1][1] = a[1][1];
	for (int i = 2; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			dp[i][j] = max(dp[i - 1][j - 1] + a[i][j], dp[i - 1][j] + a[i][j]);//表示它从左上方和上方下来两种情况并找出其中已知权值和最大的
		}
	}
	for (int i = 1; i <= n; i++)res = max(res, dp[n][i]);
	cout << res << endl;
	return 0;
}