[2216] 문자열과 점수

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

2216번: 문자열과 점수

<문제>

dp(i, j) : x[0, i), y[0, j)까지 사용했을때의 최적해로 놓고, x[i]==x[j]인 경우와 그 반대로 분기하면 되는데,

기저사례를 만드는 부분에 유의해야 한다. 0이나 -1따위를 return하는것이 아니라

한쪽을 이미 다 써버린 경우에는 (반대쪽 문자+공백)의 조합만 가능하므로 b를 남는 횟수만큼 곱해서 return해준다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int a, b, c, ans, dp[3001][3001];
string x, y;
int f(int i, int j) {
    if (i < 0) return (j + 1) * b;
    if (j < 0) return (i + 1) * b;
    if (dp[i][j] != -1) return dp[i][j];
 
    dp[i][j] = max(f(i - 1, j), f(i, j - 1)) + b;
    if (x[i] == y[j])
        dp[i][j] = max(f(i - 1, j - 1) + a, dp[i][j]);
    else
        dp[i][j] = max(f(i - 1, j - 1) + c, dp[i][j]);
    return dp[i][j];
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> a >> b >> c >> x >> y;
    int X = x.length(), Y = y.length();
    memset(dp, -1, sizeof(dp));
    cout << f(X - 1, Y - 1);
    return 0;
}