算法设计中,贪心算法和动态规划是解决最优化问题的两大核心思想。二者均聚焦于'最优解',但解题策略截然不同:贪心追求'局部最优'以逼近全局最优,动态规划则通过'记录子问题解'避免重复计算,确保全局最优。本文将从原理、适用场景、经典案例出发,结合 C++ 代码实现,深入剖析两种算法的核心逻辑与应用差异。
一、核心概念梳理
1.1 贪心算法(Greedy Algorithm)
核心思想:每一步都做出当前状态下的最优选择(局部最优),且一旦选择便不可回溯,最终期望通过一系列局部最优决策得到全局最优解。关键条件:问题需满足「贪心选择性质」(局部最优能推导出全局最优)和「最优子结构」(问题的最优解包含子问题的最优解)。优缺点:
- 优点:时间复杂度低,实现简单;
- 缺点:并非所有问题都适用,若局部最优无法导向全局最优,则贪心失效。
1.2 动态规划(Dynamic Programming, DP)
核心思想:将复杂问题拆解为若干重叠子问题,通过记录子问题的最优解(DP 表),避免重复计算,最终合并子问题解得到全局最优。关键条件:问题需满足「最优子结构」和「子问题重叠性」(子问题会被多次重复计算)。核心步骤:
- 定义状态(DP 数组 / 表的含义);
- 推导状态转移方程;
- 确定初始条件;
- 计算最优解(自底向上 / 自顶向下)。优缺点:
- 优点:能保证全局最优,适用范围广;
- 缺点:空间复杂度较高(需存储子问题解),状态转移方程设计难度大。
二、经典案例对比实现
2.1 案例 1:找零钱问题(贪心 vs 动态规划)
问题描述
给定不同面额的硬币 coins 和一个总金额 amount,求凑成该金额所需的最少硬币数。若无法凑出,返回 -1。
场景 1:硬币面额满足贪心性质(如 [1,5,10,25])
当硬币面额为规范的整数倍(如美元、人民币)时,贪心算法可直接取最大面额硬币,逐步减少金额,得到最优解。
贪心实现(C++):
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 贪心找零:仅适用于硬币面额满足贪心选择性质的场景
int greedyChange(vector<int>& coins, int amount) {
// 先将硬币按面额降序排序
sort(coins.rbegin(), coins.());
count = ;
( coin : coins) {
(amount <= ) ;
num = amount / coin;
count += num;
amount -= num * coin;
}
amount == ? count : ;
}
{
vector<> coins = {, , , };
amount = ;
res = (coins, amount);
(res == ) {
cout << << endl;
} {
cout << << res << endl;
}
;
}

