DP(2

羽島伊月 · 2021-02-04 08:56:15 · 个人记录

DP

数字三角形

1. 状态表示

• 集合：所有从起点走到( i , j ) 的路径.

• 属性：Max.

2. 状态计算

#include<bits/stdc++.h>

最长上升子序列

1. 状态表示

• 集合：所有以i个数结尾的上升子序列.

• 属性：Max.

2. 状态计算

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

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

int main()
{
  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[i],f[j]+1);
        maxn=max(maxn,dp[i]);
      }
    }
  }

  printf("%d\n",maxn);

  return 0;
}

最长公共子序列

1. 状态表示

• 集合：所有在第一个序列的前i个字母中出现,且在第二个序列的前j个字母中出现的子序列.

• 属性：Max.

2. 状态计算

#include<bits/stdc++.h>

using namespace std;
int n,m;

char a[N],b[N];
int f[N][N];

int main()
{
  cin>>n>>m;
  scanf("%s%s",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);
    }
  }

  printf("%d\n",f[n][m]);

  return 0;
}