描述

咱們就不拐彎抹角了，如題，需要你做的就是寫一個程序，得出最長公共子序列。
tip：最長公共子序列也稱作最長公共子串(不要求連續)，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個序列 S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。

輸入

第一行給出一個整數N(0<N<100)表示待測數據組數
接下來每組數據兩行，分別為待測的兩組字符串。每個字符串長度不大于1000.

輸出

每組測試數據輸出一個整數，表示最長公共子序列長度。每組結果占一行。

樣例輸入

2
asdf
adfsd
123abc
abc123abc

樣例輸出

3
6

?

?

/*動態規劃（DP）：適用于子問題不是獨立的情況，也就是各子問題包含公共的子子問題，
鑒于會重復的求解各子問題，	DP對每個問題只求解一遍，將其保存在一張表中，從而避免重復計算。實施步驟：1.將最優化問題分成若干個階段；2.將問題發展到各個階段 所處不同狀態表示出來；3.應用遞推（或遞歸）求解最優值；4.根據計算最優值時所得到的信息，構造最優解。 
*/
#include "stdio.h"
#include "string.h"
#define N 1000+10
char str1[N],str2[N];
int state[N][N];	
int main()
{int n;int size1,size2;scanf("%d",&n);if(n<=0) return 0;while(n--){scanf("%s %s",str1,str2);size1=strlen(str1); size2=strlen(str2);memset(state,0,sizeof(state));for(int y=1;y<=size1;y++){for(int x=1;x<=size2;x++){if(str1[y-1]==str2[x-1]) state[y][x]=state[y-1][x-1]+1;else state[y][x]=state[y][x-1]>state[y-1][x]?state[y][x-1]:state[y-1][x];}}		printf("%d\n",state[size1][size2]);		}return 0;
} /*//打印狀態 printf("    ");	for(int i=0;i<size2;i++) printf("%c  ",str2[i]); printf("\n");for(int x=1;x<=size1;x++){printf("%c:  ",str1[x-1]); for(int y=1;y<=size2;y++){printf("%d  ",state[x][y]);}printf("\n");}//	printf("str1=%s\nstr2=%s\n",str1,str2);for(int i=1;i<=size2;i++){if(state[size1][i]>state[size1][i-1]) printf("%c ",str1[i]);}printf("\n%d\n",state[size1][size2]);
*/

?簡單的動態規劃題可先學習《最長非降子序列》 題