首页 > 代码库 > 动态规划 LCS，LIS

动态规划 LCS，LIS

2024-07-15 19:28:02   223人阅读

1、最大连续子序列
dp[i]=max(dp[i-1]+a[i],a[i]) 以i为结尾


2、最大不连续子序列
dp[i]=max(dp[j]+a[i],dp[j])


3、最大连续递增子序列
if a[i]>a[j]
   dp[i]=max(dp[i-1]+a[i],a[i])


4、最大不连续递增子序列
if a[i]>a[j]
   dp[i]=max(dp[j]+a[i],dp[j])


5、最长不连续公共子序列
if a[i-1]==b[j-1] 
   dp[i][j]=dp[i-1][j-1]+1;
else
   dp[i][j]=max(dp[i-1][j],dp[i][j-1])


6、最长不连续递增子序列
if a[i]>a[j]
   dp[i]=max(dp[j])+1


7、最长连续递增子序列
if a[i]>a[i-1]
   dp[i]=dp[i-1]+1;


8、最长公共字串
char s1,s2;
int f=0,last=0,Max=0;
for(int i=1;i<=l1;++i)
    for(int j=l2;j>=1;--j) //必须要逆序的，正序要用2维的
       if s1[i-1]==s2[j-1]
          dp[j]=dp[j-1]+1;
       if(dp[j]>Max){
          Max=dp[j];
          last=j-1;
f=last-Max+1;
for(int i=f;i<=last;++i)
  lcs[i]=s2[i];


联系
我们