线性dp

本文主要是介绍线性dp，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一 、 数字三角形。

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

        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]; // 第二维是 斜着的列。 是选择的集合。
int a[N][N]; 

int main()
{
    int n;
    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 + 1; j ++) // 注意边界也要初始化。 所以是 i + 1；
    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 res = -INF;
    for(int i = 1; i <= n; i ++) res = max(res, f[n][i]);// 遍历所有最底层的结果。
    cout << res << endl;
}

换个思路  我们可以自下往上求解。

直接把数值存入 f 数组。可以不用初始化了。

更简单， 不用处理边界 也不用在最下层找最大值。

代码：

#include<iostream>
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 + 1] + f[i][j], f[i + 1][j + 1] + f[i][j]);

    cout << f[1][1] << endl;
}

二、 最长上升子序列。

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

输入格式

第一行包含整数 NN。

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

输出格式

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

数据范围

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

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

 之前我们遇到的本质上都是二维dp  

这个题是一维的dp

#include<iostream>
using namespace std;

const int N = 1010;
int a[1010], f[1010];
int n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    a[0] = -0x3f3f3f3f;
    for(int i = 1; i <= n; i ++)
    for(int j = 0; j <= i; j ++)
    if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1); // 因为 a[ 0 ] 设成了负无穷， 所以 f 至少为 1。

    int ans = 0;
    for(int i = 1; i <= n; i++)
    ans = max(ans, f[i]);
    
    printf("%d" , ans);
}

 y 总的思路。

for(int i = 1; i<= n; i++)

    {

        f[i] = 1; // 这是只有 a[i] 一个数时的情况。

        for(int j = 1; j < i; j ++ )  // j 从 1 开始， 因为 f [ i ] 已经 是 1。

        if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);

    }

 三 、 最长公共子序列。

给定两个长度分别为 NN 和 MM 的字符串 AA 和 BB，求既是 AA 的子序列又是 BB 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 NN 和 MM。

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

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

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

输出格式

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

数据范围

1≤N,M≤10001≤N,M≤1000

输入样例：

4 5
acbd
abedc

输出样例：

3

 用  f [ i - 1, j ]  和 f [ i , j - 1 ] 就能表示 00   01  10  三种状态所有的选择集合了。

 认清闫氏dp   f 到底表示的还是集合。

代码：

#include<iostream>
using namespace std;

const int N = 1010;

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

int main()
{
    cin  >> n >> m;
    scanf("%s%s", a + 1 ,b + 1);  从 i  =  1 处开始， 因为会用到 i - 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); 后判断 a i  == b i
    }
    cout << dp[n][m] << endl;
}

这篇关于线性dp的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！