动态规划和贪心

该博客上撰写的文章是出于教学目的而创建的。 另外，文章中的信息可能不正确，请谨慎。

动态规划和贪婪将大问题分解为更小的选择，但它们处理选择的方式不同。

Dynamic Programming

当重复相同的小问题并且可以用小问题的最优解创建大问题的最优解时使用它。

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];
}

由于存储了计算结果，因此不会重复相同的递归问题。 关键是正确建立状态定义和点火表达式。

Greedy

做出当前看来最好的选择，不要背弃之前的选择。

与活动选择问题一样，存在通过不断选择完成时间最快的任务来实现最优解决方案的问题。 然而，在硬币单位任意给定的找零问题中，首先选择最大的硬币可能不是最优的。

硬币：1、3、4
数量：6

贪婪：4 + 1 + 1 = 3
最优解：3+3=2

贪婪速度快且占用内存少，但需要证明局部最优选择会导致全局最优解。 如果仅仅因为几个例子是正确的而选择贪婪，那么在反例上就会失败。