uva 10192 - Vacation 和 uva 10066 - The Twin Towers

題目意思  ：  求最長公共子序列

解題思路：     根據最長公共子序列問題的性質，我們可以規定dp[i][j]為字符串1的前i個字符和字符串2的前j個字符的最長公共子序列的長度,  由於下面涉及到i-1和j-1，那麼這個時候我們一般從i=1和j=1開始到i<=len1, j<=len2。
                1ch1[i-1] = ch2[j-1] ,那麼dp[i][j]= dp[i-1][j-1] + 1;
             2 ch1[i-1] != ch2[j-1] ,那麼我們知道ch1[i]和ch2[j]不可能在同一個公共子序列裡出現，那麼這個時候的最長的子序列可能以ch1[i]或ch2[j]結尾，那麼由於dp[i][j]= max {dp[i-1][j] , dp[i][j-1]};  這個時候所有i=0或j=0的dp[i][j]= 0；
                            0 ; i = 0或j= 0;
就有          dp  =   dp[i][j] = dp[i-1][j-1] + 1; i > 0且j> 0 且ch1[i-1]= ch2[j-1];
                                dp[i][j]= max {dp[i-1][j] , dp[i][j-1]};i > 0且j> 0且ch1[i-1]!= ch2[j-1];

10066代碼：
[cpp] 
#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <stack> 
#include <queue> 
#include <cmath> 
using namespace std; 
#define MAXN 110 
 
int N1 , N2; 
int h1[MAXN] , h2[MAXN]; 
int dp[MAXN][MAXN]; 
int ans_max , cnt; 
 
void solve(){ 
    int i , j; 
    ans_max = 0; 
    memset(dp , 0 , sizeof(dp)); 
     
    for(i = 1 ; i <= N1 ; i++){ 
        for(j = 1 ; j <= N2 ; j++){ 
            if(h1[i-1] == h2[j-1]) 
                dp[i][j] = dp[i-1][j-1] + 1; 
            else 
                dp[i][j] = dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1]; 
            if(ans_max < dp[i][j]) ans_max = dp[i][j]; 
        } 
    } 
    printf("Number of Tiles : %d\n\n" , ans_max); 
} 
 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    cnt = 1; 
    while(scanf("%d%d" , &N1 , &N2)){ 
        if(N1 == 0 && N2 == 0) break; 
        for(int i = 0 ; i < N1; i++) scanf("%d" , &h1[i]); 
        for(int i = 0 ; i < N2; i++) scanf("%d" , &h2[i]); 
        printf("Twin Towers #%d\n" , cnt++); 
        solve(); 
    } 
    return 0; 
} 
10192 代碼：
[cpp] 
/*
最長公共子序列解法
*/ 
#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <stack> 
#include <queue> 
#include <cmath> 
using namespace std; 
#define MAXN 110 
 
int dp[MAXN][MAXN]; 
char ch1[MAXN] , ch2[MAXN]; 
int cnt , ans_max; 
 
void solve(){ 
    int i , j; 
    memset(dp , 0 , sizeof(dp)); 
    ans_max = 0 ; 
    for(i = 1 ; i <= strlen(ch1) ; i++){ 
        for(j = 1 ; j <= strlen(ch2) ; j++){ 
            if(ch1[i-1] == ch2[j-1]) dp[i][j] = dp[i-1][j-1]+1; 
            else dp[i][j] = dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1]; 
            if(ans_max < dp[i][j]) ans_max = dp[i][j]; 
        } 
    }     
} 
 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    cnt = 1; 
    while(gets(ch1)){ 
        if(strcmp(ch1 , "#") == 0) break; 
        gets(ch2); 
        solve(); 
        printf("Case #%d: you can visit at most %d cities.\n" , cnt++ , ans_max); 
    } 
    return 0; 
}