백준 9251, dp, LCS (2가지 방법)

문제

https://www.acmicpc.net/problem/9251

유명한 문제 최장공통 부분 수열

해결방법

dp top down을 두가지 방식으로 했다.

• dp[i][j] = > 문자열 a를 i번째보고 있고, 문자열 b를 j번째 보고 있을때 최장 공통 부분수열의 길이이다.

if (str1[x] == str2[y]) {
        dp[x][y] = solve(x - 1, y - 1) + 1;
    }
    else {
        dp[x][y] = max(solve(x - 1, y), solve(x, y - 1));
    }

• 위에서 현재 보고있는 x, y에서 같은 문자일때는 dp[x][y] = 이전dp + 1 , 다를 때는 둘중에서 하나만 골랐을 때 최장이 나온 것을 선택하면된다.
• 차이, 주의
• 예전에는 top down방식이긴하나 거꾸로해서 dp[i][j] = solve( i + 1, j + 1).. 이런식으로 i, j위치에서 다음 위치를 재귀로 돌렸다.. 익숙하지 않아서 그냥 top -down 뒤로갈꺼면 제대로 뒤로가자고 뒤로 돌렸다

• 주의할점은 1번 베이스를 하고있을 때는 cin >> str1 >> str2가 안된다 이렇게하면 str1의 처음은 .begin()으로 잡아버려서 0베이스가 된다. 그래서 그냥 0베이스로 풀었다.

소스

#include <bits/stdc++.h>

using namespace std;

//dp[i][j] a를 i번째 보고있고 b를 j번째를 보고있다 .
//문자열길이 1 ~ n, 1 ~ m으로 보자 
int dp[2000][2000];
string str1, str2;
int n, m;
int solve(int x, int y) {

    if (x < 0 || y < 0) return 0;

    if (dp[x][y] != -1) return dp[x][y];

    dp[x][y] = 0;

    if (str1[x] == str2[y]) {
        dp[x][y] = solve(x - 1, y - 1) + 1;
    }
    else {
        dp[x][y] = max(solve(x - 1, y), solve(x, y - 1));
    }

    return dp[x][y];
}

int main() {

    memset(dp, -1, sizeof(dp));
    cin >> str1 >> str2;   // 0 base가 된다 

    n = (int)str1.size();
    m = (int)str2.size();


    cout << solve(n -1, m -1);
}