解決問題的策略思路和解決的問題類型差異

• 動態規劃：動態規劃通常涉及將問題分解為子問題，然後將子問題的解合並以獲得原始問題的解。它涉及到構建一個表格，以存儲子問題的解，以避免在解決同一子問題時進行重覆計算。動態規劃通常更適用於最優化問題。
• 貪心算法：貪心算法在每一步都選擇當前狀態下的最佳選擇，而不考慮全局最優解。它會一直選擇局部最優解，直到獲得全局最優解。貪心算法通常用於解決問題的近似最優解。

問題類型：
動態規劃：動態規劃通常適用於具有重疊子問題和最優子結構性質的問題，例如最短路徑問題、背包問題等。這些問題可以分解為子問題，並且子問題的解可以用來解決原始問題。
貪心算法：貪心算法適用於具有貪心選擇性質的問題，即每一步都選擇當前狀態下的最佳選擇，而不考慮全局最優解。貪心算法通常用於最優化問題，但並非所有最優化問題都適用於貪心策略。

白話來說動態規劃更加靈活，可以解決更廣泛類型的問題，但通常需要花費更多的計算時間。貪心算法則更加簡單且高效，但可能不適用於所有類型的問題。因此，在選擇解決方法時，需要根據具體問題的特點來決定使用動態規劃還是貪心算法～

假設有一個問題：給定一個整數數組，找到一個連續的子數組，使得子數組的和最大。我們稱這個問題為最大子數組和問題。
例如，對於數組 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，最大的連續子數組是 [4, -1, 2, 1]，它的和是 6。

解決方案分析：
動態規劃：
動態規劃可以有效解決最大子數組和問題。我們可以定義一個動態規劃數組 dp，其中 dp[i] 表示以第 i 個元素結尾的子數組的最大和。狀態轉移方程可以定義為：
dp[i] = max(nums[i], nums[i] + dp[i-1])
這種方法適用於最大子數組和問題，因為它具有重疊子問題和最優子結構性質。
貪心算法：
貪心算法在這個問題上並不適用，因為它無法保證局部最優解會導致全局最優解。例如，在數組 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 中，如果我們只考慮局部最優解，可能會選擇子數組 [4, -1, 2, 1]，但這並不是全局最優解。