Longest Common Subsequence & & Substirng [공통 하위 시퀀스 및 하위 문자열] [클래식 dp]

제목 1: Longest Common Subsequence
내용: a, b 두 문자열을 제시하고 가장 긴 공통 서열의 길이를 구합니다!
사고방식: 하위 서열: 문자열의 임의의 위치에 있는 문자를 골라서 구성하고 순서가 원래의 순서를 유지하는 문자열을 하위 서열로 한다!
dp[i][j]는 상태를 나타낸다. a 문자열에서 i번째 위치와 b 문자열에서 j번째 위치까지의 공통 길이가 가장 좋다!
dp[][]는 모두 4가지: dp[i-1][j-1], dp[i-1][j], dp[i][j-1], dp[i][j];
그래서 a[i]==b[i]일 때 dp[i][j]=dp[i-1][j-1]+1(dp[i-1][j-1]이 지난번과 같았을 때의 최우선이기 때문)
a[i] != b[i]시 dp[i][j]=max(dp[i-1][j], dp[i][j-1])(지난번 같지 않은 것 중 가장 좋은 것 중에서 가장 좋은 것 선택)
코드:

#include 
#include 
#include 
using namespace std;
const int maxn = 1005;
int dp[maxn][maxn];
int main()
{
    char a[maxn],b[maxn];
    while(scanf("%s%s",a,b)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        int n = strlen(a),m = strlen(b);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(a[i-1] == b[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
",dp[n][m]);
    }
    return 0;
}

제목 2: Longest Common Substirng
내용: a, b 두 문자열, 공통 연속 하위 문자열의 길이를 구합니다!
사고방식: 동상,
a[i]=b[i]일 때 dp[i][j]=dp[i-1][j-1]+1
하지만 a[i]!=b[i]일 때는 다르다. 연속적인 문자열이 필요하기 때문에 현재 dp[i][j]를 직접 끊으면 된다. 즉, dp[i][j]=0이다.
마지막으로 dp[][]에서 최대 값을 선택하면 가장 긴 공통 연속 문자열입니다!
코드:

#include 
#include 
#include 
using namespace std;
const int maxn = 1005;
int dp[maxn][maxn];
int main()
{
    char a[maxn],b[maxn];
    while(scanf("%s%s",a,b)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        int n = strlen(a),m = strlen(b),ans = 0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = 0;
                ans = max(ans,dp[i][j]);
            }
        printf("%d
",ans);
    }
    return 0;
}