DP

Dynamic Programming의 약자로 하나의 문제를 한 번만 푸는게 핵심이다.

문제를 작은 문제로 쪼개어 풀고, 푼 결과를 기억해 결과의 합으로 본래의 문제의 해를 구하는 방식이다.

대표적인 예로 피보나치 수열이 있다. f(x) = f(x-1) + f(x-2)

---

예제문제. 이동 비용이 있는 계단에서 n번째 계단까지 가기위한 최소 비용 구하기

#include <iostream>
#include <vector>

using namespace std;

int minCostStairs(vector<int>& vec, int target)
{
    int maxCoins = 999999;
	
    vector<int> dp(target + 1, 0);

    // 계단을 한번에 1칸 또는 2칸 올라갈 수 있다.
    dp[0] = 0;
    dp[1] = 0;

    for (int i = 2; i < target; ++i)
    {
        // 직전 칸까지의 dp와 추가로 붙는 cost
        // 직직전 칸까지의 dp와 추가로 붙는 cost 중 최소 값을 가져온다
        dp[i] = min(dp[i - 1] + vec[i - 1], dp[i - 2] + vec[i - 2]);
    }

    return dp[target - 1];
}

int main()
{
    vector<int> vec = {1,2,4,6,2,4,6,1};
    cout << minCostStairs(vec, 7) << endl;
    return 0;
}

---

예제문제. 코인의 종류와 목표 값이 주어졌을 때, 목표 값을 구성할 수 있는 코인의 갯수 구하기

#include <iostream>
#include <vector>

using namespace std;

int coinAmount(vector<int>& vec, int amount)
{
    // 달성할 수 없는 코인 갯수
    int maxCoins = 999999;
	
    vector<int> dp(amount + 1, 0);

    // 주어진 코인이랑 동일한 dp는 채워넣기
    for (int coin : vec)
        dp[coin] = 1;

    // 1부터 원하는 값까지 dp 데이터를 채워넣는다
    for (int i = 1; i <= amount; ++i)
    {
        // 이미 채워진 결과는 다시 할 필요 없음
        if (0 < dp[i])
            continue;

        int minCount = maxCoins;

        // 주어진 코인 종류로 체크해보자
        for (int coin : vec)
        {
            // 코인보다 적게 남았으면 패스
            if (coin > i)
                continue;

            // 이전 데이터가 없다
            if (dp[i- coin] == 0)
                continue;

            // n은 coin과 n-coin으로 구성되어있다.
            // n-coin의 dp값과 현재 코인 갯수(1)을 더한 값과 비교해서 최소값을 구한다
            minCount = std::min(minCount, dp[i - coin] + 1);
        }

        dp[i] = minCount;
    }

    return dp[amount];
}

int main()
{
    vector<int> vec = {2,3,5};
    cout << coinAmount(vec, 1000) << endl;
    return 0;
}