程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Common Subsequence(HDU

Common Subsequence(HDU

編輯:關於C++

最長公共子序列,其實就是最長上升子序列的變形。 dp[i][j]表示以第一個序列的i位置為結尾和以第二個序列的j位置為結尾的子序列的公共子序列的長度。

顯然影響決策的因素就是這兩個序列的位置,所以二重循環直接搞就行了,如果這兩個位置的字符相同就+1

 

#include
#include
#include
#include
#include
using namespace std;
char s1[10000],s2[10000],s[10000];
int d[999][999];
int main(){
    while(~scanf("%s",s1)){
        memset(d,0,sizeof(d));
        scanf("%s",s2);
        int n = strlen(s1),m=strlen(s2);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s1[i-1]==s2[j-1]) d[i][j] = d[i-1][j-1] + 1;
                else d[i][j] = max(d[i-1][j],d[i][j-1]);
            }
        }
        printf("%d\n",d[n][m]);
    }
    return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved