Dynamic Programming and Greedy

The articles written on this blog were created with the goal of teaching. Also, the information in the article may be incorrect, so please be careful.

Dynamic Programming and Greedy break big problems into smaller choices, but they deal with choices differently.

Dynamic Programming

It is used when the same small problem is repeated and the optimal solution to the large problem can be created with the optimal solution to the small problem.

int Fibonacci(int N)
{
    if (N <= 1)
    {
        return N;
    }

    std::vector<int> DP(N + 1, 0);
    DP[1] = 1;

    for (int i = 2; i <= N; ++i)
    {
        DP[i] = DP[i - 1] + DP[i - 2];
    }

    return DP[N];
}

Because the calculated results are stored, the same recursive problem is not repeated. The key is to properly establish state definitions and ignition expressions.

Greedy

Make the choice that seems best in the present moment and don't go back on your previous choice.

Like the activity selection problem, there are problems where the optimal solution is achieved by continuously selecting the task with the fastest finish time. However, in the change problem where the coin units are given arbitrarily, selecting the largest coin first may not be optimal.

Coins: 1, 3, 4
Amount: 6

Greedy: 4 + 1 + 1 = 3
Optimal solution: 3 + 3 = 2

Greedy is fast and uses little memory, but requires proof that local optimal selection leads to a global optimal solution. If you choose Greedy just because a few examples are correct, it will fail on the counterexamples.