[1143] Longest Common Subsequence

看起來是很基本的DP

我還是砍掉重練吧(倒地)

1.用一個二維array 分別代表text1 跟text2 , 必須都多加一格前置單元init到 0

2.開始一個一個比, 從index 從array的(1,1) 開始, 但是比對的text是從index 0 開始所以比字元的時候用的是是 i-1 跟 j-1

3. 如果相同, 取左上加一; 如果不同, 取 左邊 或 上面 的大的那一個

優化: 

因為只會拿到左上, 左, 跟上, 所以其實用 兩條array去存就可以了, 但我現在懶XD（被毆飛）

#define MAX(A,B) (A>B)?A:B;

int longestCommonSubsequence(char * text1, char * text2){

int l1= strlen(text1)+1;

int l2= strlen(text2)+1;

int** dp = malloc(sizeof(int*)*l1);

for (int i=0;i<l1;i++)

dp[i]= calloc (l2,sizeof(int));

for (int i=1;i<l1;i++)

for (int j=1;j<l2;j++)

{

//printf("%d %d %c %c\n",i , j, text1[i-1],text2[j-1]);

if (text1[i-1]==text2[j-1])

dp[i][j]=dp[i-1][j-1] +1;

else

dp[i][j]=MAX(dp[i-1][j],dp[i][j-1]);

}

return dp[l1-1][l2-1];

}