Greedy Algorithm

Greedy Algorithm 是一種常見的演算法設計方法，通常用於求解最佳化問題。

它的基本思想是在每一步都做出當前看起來最有利的選擇，而不考慮整體問題的未來發展。

換句話說，貪婪演算法每次都選擇局部最優解，希望通過這種方式達到全局最優解。

貪婪演算法的特點是它不進行回溯或考慮可能的後果，只關注當前的最佳選擇，因此適用於某些特定的問題類型。

然而，由於它的貪婪性質，貪婪演算法不能保證總是找到全局最佳解，因此在某些情況下可能會產生次優解。

What difference with Dynamic Programming

它們在解決問題時的策略和思維方式有所不同，但有時候也可以相互影響。

1. 貪婪算法（Greedy Algorithm）：

   • 貪婪算法通常用於優化問題，其中目標是找到最佳解或近似最佳解。
   • 貪婪算法的主要思想是每次都選擇當前看起來最好的選擇，而不考慮未來的影響。
   • 貪婪算法不會回頭更正之前的決策，它只關注當前局部最佳解。
   • 貪婪算法的時間複雜度通常較低，但不能保證找到全局最佳解。

2. 動態規劃（Dynamic Programming，DP）：

   • 動態規劃通常用於解決具有遞迴結構的問題，其中目標是找到最優解。
   • DP使用記憶化技巧，將子問題的解存儲起來，以避免重複計算，這種方法通常被稱為"最優子結構"。
   • DP能夠確保找到全局最優解，但時間複雜度通常較高，因為它需要處理和計算許多子問題。

貪婪算法和動態規劃之間的關係在於，有時候可以使用貪婪算法來解決一些特殊的問題，並且貪婪算法可能在特定情況下提供足夠好的解答。

然而，貪婪算法無法保證解的最優性，而動態規劃則更適合確保最優解的問題，但通常需要更多的計算時間。

接下來進入到 Greedy Algorithm 的世界 !!!