线性DP问题

DP时间复杂度

时间复杂度等于状态数量乘以计算每一个状态所需要的时间

ACWING898数字三角形

思想

这是三角形在数组中的排列方式
注意边界问题，以及初始化要把数组值初始化成负无穷（因为数据有负数）

#include
using namespace std;
const int RES = 1e9;
const int MAXN=1005;
int dp[MAXN][MAXN];
int a[MAXN][MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int i,j,n,ans=-RES;
    cin>>n;
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
            {
                a[i][j]=-RES;
                dp[i][j]=-RES;
            }
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
    {
        cin>>a[i][j];
    }
    
    dp[1][1]=a[1][1];
    for(i=2;i<=n;i++)
        for(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(j=1;j<=n;j++)
    {
        ans=max(dp[n][j],ans);
    }
    cout<<ans<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

ACWING895 最长上升子序列

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

输入格式
第一行包含整数 N 。

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

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

数据范围

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

输入样例：

7
3 1 2 1 8 5 6
1
2

输出样例：

4
1

思想

代码略

注意：如果想输出最长上升子序列，只需新开一个数组记录倒数第二个数的位置即可

ACWING897最长公共子序列

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

输入格式
第一行包含两个整数 N 和 M 。

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

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

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

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

数据范围

1≤N,M≤1000 
1

输入样例：

4 5
acbd
abedc
1
2
3

输出样例：

3
1

思想
求最大值，子问题可以重复，不漏掉就没问题（但求数量的，子问题不能重复）
比如A和B构成C，A和B有重复的地方
那么求集合C中的最大值，只需先求集合A的最大值，再求集合B的最大值，最后再把两个最大值比较，最后求出的最大值就是C的最大值

状态计算比较复杂，分为四种情况：
00：不包括i也不包括j
01：包括j但不包括i
10：包括i但不包括j
11：包括i也包括j

注意
1.f[i-1][j-1]已经在后三种情况中了，所以实际上只需考虑后三种情况
2.f[i-1][j]和f[i][j-1]和“只出现j，没出现i”“只出现i，没出现j”的概念是不同的，但因为前两者包括后两者，所以可以通过求前两者的最大值求出整体的最大值（上面ABC的例子）

代码：

#include 
using namespace std;
const int N=1010;
char a[N],b[N];
int f[N][N];
int main()
{
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    scanf("%s%s",a+1,b+1);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            f[i][j]=max(f[i][j-1],f[i-1][j]);
            if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    printf("%d",f[n][m]);
    return 0;
}
/*10 10
nqunjucfgh
irsfovvqah*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23