다이나믹 프로그래밍과 메모제이션 문제

dp 문제를 풀 때는 항상 메모제이션이 적용될 수 있는지 생각해보자.

 

dp와 메모제이션은 말로 풀어서 설명해보면 쉽게 구현할 수 있다.

 

예를 들어 아래 문제 배낭의 메모제이션은 가방에 index를 넣을 수 있는 차례고 (index는 순차적으로 연산됨. 중복될 수 없음.) weight만큼 들어갈 수 있을 때 최대 가치는? 라는 뜻으로 이용하면 된다. 그리고 메모제이션은 초기값이 아니면 항상 같은 값을 반환하는 함수처럼 작동한다.

 

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

// 다른 사람이 푼 깔끔한 코드
#include <iostream>
#include <algorithm>

using namespace std;

int N = 0, K = 0;
int V[101] = {0,};
int W[101] = {0,};
int dp[101][100001] = {0,};

int main()
{
    cin >> N >> K;

    for(int i = 1; i <= N; i++)
        cin >> W[i] >> V[i];

    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= K; j++)
        {
            if(W[i] <= j) dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]]+V[i]);
            else dp[i][j] = dp[i-1][j];
        }
    }

    cout << dp[N][K];

    return 0;
}

#define INF 987654321
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, k;
int stuff[100][2];
int cache[100001][100];

int solve(int index, int weight) {
    if (weight < 0) return -INF;
    if (index >= n)return 0;
    if (weight == 0) return 0;
    int& ret = cache[weight][index];
    if (ret != -1) return ret;
    ret = max(
        solve(index + 1, weight - stuff[index][0]) + stuff[index][1],
        solve(index + 1, weight)
    );
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    for (int i = 0; i < 100001; i++)
        for (int j = 0; j < 100; j++)
            cache[i][j] = -1;

    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> stuff[i][0] >> stuff[i][1];

    cout << solve(0, k);
    return 0;
}

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

#define INF 987654321
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

string s;
vector<string> v;
int cache[50][50] = { 0 };

int get_cost(int begin, int windex) {
    int length = v[windex].length();
    int arr[50] = { 0 };
    int ret = 0;
    for (int i = 0; i < length; i++) {
        arr[s[begin + i] - 'a']++;
        arr[v[windex][i] - 'a']--;
        if (s[begin + i] != v[windex][i]) ret++;
    }
    for (int i = 0; i < 26; i++) {
        if (arr[i] != 0) return -1;
    }
    return ret;
}

int solve(int begin, int windex) {
    if (begin >= s.length()) return 0;

    int& ret = cache[begin][windex];
    if (ret != -1) return ret;

    ret = INF;
    int cost = get_cost(begin, windex);
    if (cost < 0) return INF;

    int next = begin + v[windex].length();
    for (int i = 0; i < v.size(); i++)
        ret = min(ret, solve(next, i));
    ret += cost;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    for (int i = 0; i < 50; i++)
        for (int j = 0; j < 50; j++)
            cache[i][j] = -1;

    int n;

    cin >> s;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string q; cin >> q; v.push_back(q);
    }

    int ans = INF;
    for (int i = 0; i < n; i++)
        ans = min(ans, solve(0, i));
    cout << (ans == INF ? -1 : ans);

    return 0;
}