编辑“︁贪心算法与动态规划对比”︁

== 贪心算法与动态规划对比 ==

贪心算法（Greedy Algorithm）和动态规划（Dynamic Programming）是解决优化问题的两种重要方法。它们在算法设计中有着广泛的应用，但解决问题的思路和适用场景有显著差异。本节将详细对比这两种方法，帮助读者理解它们的核心思想、优缺点以及适用条件。

=== 基本概念 ===

'''贪心算法'''是一种在每一步选择中都采取当前状态下最优（即局部最优）的选择，从而希望导致全局最优解的算法。贪心算法通常高效，但不保证总能得到最优解。

'''动态规划'''则是通过将问题分解为相互重叠的子问题，并存储子问题的解（通常使用表格），避免重复计算，从而高效地解决复杂问题。动态规划通常能保证得到最优解，但可能需要更多的计算资源。

=== 核心区别 ===

{| class="wikitable"
|+ 贪心算法与动态规划对比
! 特性 !! 贪心算法 !! 动态规划
|-
| '''最优性''' || 不保证全局最优 || 保证全局最优
|-
| '''时间复杂度''' || 通常较低（如O(n)或O(n log n)） || 通常较高（如O(n²)或O(n³)）
|-
| '''空间复杂度''' || 通常较低 || 可能较高（需存储子问题解）
|-
| '''适用条件''' || 问题具有贪心选择性质 || 问题具有最优子结构和重叠子问题
|-
| '''实现难度''' || 较简单 || 较复杂
|}

=== 贪心选择性质 vs 最优子结构 ===

贪心算法的关键在于'''贪心选择性质'''：即通过局部最优选择能够达到全局最优。例如，在[[霍夫曼编码]]中，每次选择频率最小的两个节点合并，最终生成的编码树是最优的。

动态规划的关键在于'''最优子结构'''：即问题的最优解包含其子问题的最优解。例如，在[[背包问题]]中，全局最优解可以通过组合子问题的最优解得到。

=== 示例对比：找零问题 ===

==== 贪心算法示例 ====
贪心算法在找零问题（使用最少的硬币数）中可能有效，前提是硬币面额具有特定性质（如美国的硬币系统）。

<syntaxhighlight lang="python">
def greedy_coin_change(coins, amount):
    coins.sort(reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result if amount == 0 else None

# 示例
coins = [25, 10, 5, 1]
amount = 63
print(greedy_coin_change(coins, amount))  # 输出: [25, 25, 10, 1, 1, 1]
</syntaxhighlight>

'''输入''': 硬币面额 `[25, 10, 5, 1]`，金额 `63`  
'''输出''': `[25, 25, 10, 1, 1, 1]`  
'''解释''': 贪心算法每次选择最大可能的硬币，最终使用了6枚硬币。

==== 动态规划示例 ====
如果硬币面额不满足贪心性质（如 `[4, 3, 1]`，金额 `6`），贪心算法会失败（输出 `[4, 1, 1]` 而不是 `[3, 3]`）。此时需用动态规划：

<syntaxhighlight lang="python">
def dp_coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# 示例
coins = [4, 3, 1]
amount = 6
print(dp_coin_change(coins, amount))  # 输出: 2 (3 + 3)
</syntaxhighlight>

'''输入''': 硬币面额 `[4, 3, 1]`，金额 `6`  
'''输出''': `2`  
'''解释''': 动态规划计算每个子问题的最优解，最终得到最少硬币数为2。

=== 实际应用场景 ===

* '''贪心算法'''：  
  - 霍夫曼编码（数据压缩）  
  - Dijkstra算法（最短路径，无负权边）  
  - 最小生成树（Prim/Kruskal算法）

* '''动态规划'''：  
  - 背包问题  
  - 最长公共子序列  
  - 股票买卖问题（LeetCode）

=== 如何选择方法？ ===

1. '''验证贪心性质'''：若问题满足贪心选择性质，优先用贪心算法。  
2. '''检查子问题重叠'''：若问题可分解为重叠子问题，用动态规划。  
3. '''效率权衡'''：贪心算法更高效，但动态规划更通用。

=== 总结 ===

贪心算法和动态规划各有优劣：  
* 贪心算法简单高效，但适用性有限。  
* 动态规划保证最优解，但资源消耗较高。  
理解它们的差异和适用场景，是算法设计中的重要技能。

<mermaid>
graph TD
    A[优化问题] -->|具有贪心选择性质| B(贪心算法)
    A -->|具有最优子结构| C(动态规划)
    B --> D[高效但不保证最优]
    C --> E[保证最优但复杂]
</mermaid>

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:贪心算法]]