動態規劃與貪心

該部落格上撰寫的文章是出於教學目的而創建的。 另外，文章中的資訊可能不正確，請謹慎。

動態規劃和貪婪將大問題分解為更小的選擇，但它們處理選擇的方式不同。

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

貪婪速度快且佔用記憶體少，但需要證明局部最優選擇會導致全域最優解。 如果僅僅因為幾個例子是正確的而選擇貪婪，那麼在反例上就會失敗。