学步园

小记：看题意，我以为是求最长递增子序列，但是看sample又不对，于是去看了discuss，发现原来是lcs。。。

思路：lcs是经典的dp问题，最好自己动手，想出dp转移方程

dp[i][j] 表示 第一串的前i个字符和第二串的前j个字符 的最长公共子序列(lcs)的长度

那么状态转移方程即为：

dp[i][j] = a[i-1] == b[j-1]? dp[i-1][j-1]+1: max(dp[i-1][j], dp[i][j-1]); (a,b为两个字符串)

之所以是a[i-1]  b[j-1]是因为字符串都是从0开始的

我之前的一个代码，预处理一个字符与另一串比较的结果，预处理错了，导致wa了2次

	for(int i = 0; i < len2; ++i){
            if(str1[0] == str2[i]){
                dp[0][i] = 1;
            }
            else {
                dp[0][i] = 0;
            }
        }
        for(int i = 0; i < len1; ++i){
            if(str1[i] == str2[0]){
                dp[i][0] = 1;
            }
            else {
                dp[i][0] = 0;
            }
        }
        for(int i = 1; i < len1; ++i){
            for(int j = 1; j < len2; ++j){
                if(str1[i] == str2[j]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else {
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        printf("%d\n", dp[len1-1][len2-1]);

这个的问题，在于预处理，例如a和ab，答案输出为0，这就是原因

改了就好了

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-8

const int MAX_ = 510;
const int N = 100010;
const int INF = 0x7fffffff;

int dp[MAX_][MAX_];

char str1[MAX_], str2[MAX_];
int len1, len2;

int main(){

	while(~scanf("%s%s", str1,str2)){
        len1 = strlen(str1);
        len2 = strlen(str2);

        for(int i = 0; i < len2; ++i){
                dp[0][i] = 0;
        }
        for(int i = 0; i < len1; ++i){
                dp[i][0] = 0;
        }

        for(int i = 1; i <= len1; ++i){
            for(int j = 1; j <= len2; ++j){

                if(str1[i-1] == str2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else {
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }

            }
        }

        printf("%d\n", dp[len1][len2]);
	}
	return 0;
}

这样交上去对了，但是预处理明显没对dp[0][len]进行初始化，这肯定是测试数据没有测试到，所以最好加上