线性DP例题

目录

一、数字三角形

 二、最长上升子序列

三、最长公共子序列

---

一、数字三角形

题目：

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

输入格式：

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

输出格式：

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

数据范围：

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

输入样例：

5

7

3 8

8 1 0 

2 7 4 4

4 5 2 6 5

输出样例

30

题解： 

        这道题是一个经典的线性dp题 ；

        思路是，从地往上走，f[ i ][ j ]存储从底层走到第i行第j个点的所有路径中的最大值；每一个点的f[ i ][ j ]所存的点都是走到当前点的最大值；

       如何更新f[ i ][ j ]中的每一个点，每一个点所得的值可以有两种方式，一个是下一层的第j个数加上来，另一个是从下一层的第 j + 1个数加上来；所以从这两个树中取最大值加上这个位置的数值就是此位置的最大路径值；

代码如下：

#include
using namespace std;
const int N=510;
int f[N][N];
int n;
 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>f[i][j];
        }
    }
 
    for(int i=n;i>=1;i--){
        for(int j=i;j>=1;j--){
            f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j];
        }
    }
    cout<1][1]<
return 0;
}

 二、最长上升子序列

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

输入格式：

第一行包含整数 N。

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

输出格式：

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

数据范围：

1≤N≤1000，−10^9 ≤ 数列中的数 ≤ 10^9

输入样例：

7

3 1 2 1 8 5 6

输出样例：

4

题解：

        这道题依旧用数组f存下当前的状态，所谓当前的状态就是，当前位置为最大值和它前面的数所形成的最大上升子序列的长度；

      如何更新f[ i ]？每次更新f[ i ]的时候从头开始循环；找到有比a[ i ]小的数的时候，取这个小于a[ i ]的f+1 与f[ i ]中的最大值；

代码如下：
 

#include
#include
using namespace std;
int a[1010],f[1010];
int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i <= n;i ++){
        f[i] = 1;
        for(int j = 1;j < i;j ++)
            if(a[i] > a[j]) f[i] = max(f[j] + 1,f[i]);
    }
    int ans = f[1];
    for(int i = 1;i <= n;i ++) 
    ans = max(ans , f[i]);
    cout << ans << endl;
    return 0;
}

三、最长公共子序列

题目：

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

输入格式：

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

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

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

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

输出格式：

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

数据范围：

1≤N,M≤1000

输入：

4 5

acbd

abedc

输出：

 题解：

        此题依旧用f[ i ][ j ]存储状态；表示的是a串在第i个字符，b串在第j个字符时，当前的最长公共子序列；

        如何更新f[ i ][ j ] ? 分为两种情况，遍历for（i）和for（j），如果ai等于bi，f[ i ][ j ]就是等于f[ i - 1 ][j - 1] + 1;如果不相等，取f[i - 1][j]和 f[i][j - 1]中的最大值；

代码如下：

#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++) {
      if (a[i] == b[j]) {
        f[i][j] = f[i - 1][j - 1] + 1;
      } else {
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);
      }
    }
  }
  cout << f[n][m] << '\n';
  return 0;
}