2016huasacm暑假集训训练五 C-Common Subsequence

题目链接： https://vjudge.net/contest/126708#problem/C

题意：这是一道求字符串的公共子串的最大长度的题目，用dp动态方程即可

if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;

else dp[i][j]=(dp[i][j-1]>p[j][i-1]?dp[i][j-1]:p[j][i-1]);

这题主要是要注意两个字符串是同一行输入，题目没说字符串的长度，用c不是dp数组开大了编译不了就是开小了运行错误，错了几次就采用java的字符串来写，因为Java的数组可以根据字符串的长度来开，就不需要担心数组越界或者数组开小了；

AC代码：

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    static int dp[][];

    public static void main(String[] args) {

        Scanner s = new Scanner(new BufferedInputStream(System.in));
        while (s.hasNext()) {
            String a = s.next(), b = s.next();
            int len1 = a.length(), len2 = b.length();

            dp = new int[len1 + 1][len2 + 1];      //按字符串的长度开DP数组
            for (int i = 0; i <= len1; i++)
                for (int j = 0; j <= len2; j++)
                    dp[i][j] = 0;

            for (int i = 1; i <= len1; i++)
                for (int j = 1; j <= len2; j++)
                    if (a.charAt(i - 1) == b.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
            System.out.println(dp[len1][len2]);
        }
        s.close();
    }

}