算法设计中，贪心算法和动态规划是解决最优化问题的两大核心思想。二者均聚焦于 “最优解”，但解题策略截然不同：贪心追求 “局部最优” 以逼近全局最优，动态规划则通过 “记录子问题解” 避免重复计算，确保全局最优。本文将从原理、适用场景、经典案例出发，结合 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++）：
cpp
运行
#include <iostream> #include <vector> #include <algorithm> using namespace std; // 贪心找零：仅适用于硬币面额满足贪心选择性质的场景 int greedyChange(vector<int>& coins, int amount) { // 先将硬币按面额降序排序 sort(coins.rbegin(), coins.rend()); int count = 0; for (int coin : coins) { if (amount <= 0) break; // 尽可能多取当前最大面额的硬币 int num = amount / coin; count += num; amount -= num * coin; } // 若剩余金额不为0，说明无法凑出 return amount == 0 ? count : -1; } int main() { vector<int> coins = {1,5,10,25}; // 满足贪心性质的面额 int amount = 41; int res = greedyChange(coins, amount); if (res == -1) { cout << "无法凑出金额" << endl; } else { cout << "最少硬币数（贪心）：" << res << endl; // 输出：4（25+10+5+1） } return 0; }场景 2：硬币面额不满足贪心性质（如 [1,3,4]）
若硬币面额为[1,3,4]，目标金额为 6，贪心会选择4+1+1（3 枚），但最优解是3+3（2 枚）。此时需用动态规划。
动态规划实现（C++）：
cpp
运行
#include <iostream> #include <vector> #include <climits> using namespace std; // 动态规划找零：通用解法 int dpChange(vector<int>& coins, int amount) { // 定义dp数组：dp[i]表示凑成金额i所需的最少硬币数 vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; // 初始条件：凑0元需要0枚硬币 // 遍历所有金额，计算每个金额的最少硬币数 for (int i = 1; i <= amount; ++i) { // 遍历所有硬币面额，尝试更新dp[i] for (int coin : coins) { if (i >= coin && dp[i - coin] != INT_MAX) { dp[i] = min(dp[i], dp[i - coin] + 1); } } } return dp[amount] == INT_MAX ? -1 : dp[amount]; } int main() { vector<int> coins = {1,3,4}; // 不满足贪心性质的面额 int amount = 6; int res = dpChange(coins, amount); if (res == -1) { cout << "无法凑出金额" << endl; } else { cout << "最少硬币数（DP）：" << res << endl; // 输出：2 } return 0; }2.2 案例 2：最长递增子序列（LIS）—— 动态规划经典应用
贪心虽可优化 LIS 的时间复杂度，但基础解法为动态规划。
问题描述
给定一个整数数组nums，找到其中最长严格递增子序列的长度。
动态规划实现（C++）：
cpp
运行
#include <iostream> #include <vector> #include <algorithm> using namespace std; // 动态规划解LIS：时间复杂度O(n²) int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; // 定义dp数组：dp[i]表示以nums[i]结尾的最长递增子序列长度 vector<int> dp(n, 1); // 初始条件：每个元素自身是长度为1的子序列 int maxLen = 1; for (int i = 1; i < n; ++i) { // 遍历i之前的所有元素，更新dp[i] for (int j = 0; j < i; ++j) { if (nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j] + 1); } } maxLen = max(maxLen, dp[i]); } return maxLen; } // 贪心+二分优化LIS：时间复杂度O(n log n) int lengthOfLIS_Greedy(vector<int>& nums) { vector<int> tails; // tails[i]表示长度为i+1的递增子序列的最小末尾元素 for (int num : nums) { // 二分查找第一个大于等于num的位置 auto it = lower_bound(tails.begin(), tails.end(), num); if (it == tails.end()) { tails.push_back(num); // 可以延长子序列 } else { *it = num; // 替换，优化末尾元素，为后续更长序列做准备 } } return tails.size(); } int main() { vector<int> nums = {10,9,2,5,3,7,101,18}; cout << "LIS长度（DP）：" << lengthOfLIS(nums) << endl; // 输出：4 cout << "LIS长度（贪心+二分）：" << lengthOfLIS_Greedy(nums) << endl; // 输出：4 return 0; }2.3 案例 3：活动选择问题 —— 贪心经典应用
问题描述
给定多个活动的开始时间和结束时间，选择最多的互不重叠活动。
贪心实现（C++）：
cpp
运行
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Activity { int start; int end; }; // 贪心策略：选择结束时间最早的活动 int activitySelection(vector<Activity>& acts) { // 按结束时间升序排序 sort(acts.begin(), acts.end(), [](const Activity& a, const Activity& b) { return a.end < b.end; }); int count = 1; // 至少选第一个活动 int lastEnd = acts[0].end; // 遍历剩余活动，选择不重叠的 for (int i = 1; i < acts.size(); ++i) { if (acts[i].start >= lastEnd) { count++; lastEnd = acts[i].end; } } return count; } int main() { vector<Activity> acts = {{1,2}, {3,4}, {0,6}, {5,7}, {8,9}, {5,9}}; cout << "最多可选择的活动数：" << activitySelection(acts) << endl; // 输出：4 return 0; }三、贪心与动态规划的核心差异
| 维度 | 贪心算法 | 动态规划 |
|---|---|---|
| 决策方式 | 局部最优，一步到位，不可回溯 | 全局最优，记录子问题解，逐步推导 |
| 子问题关系 | 子问题无重叠，独立决策 | 子问题重叠，需复用解 |
| 适用场景 | 满足贪心选择性质的问题 | 最优子结构 + 子问题重叠的问题 |
| 时间复杂度 | 通常更低（如 O (n)、O (n log n)） | 较高（如 O (n²)、O (nm)） |
| 空间复杂度 | 通常 O (1) 或 O (n) | 需存储 DP 表，O (n) 或 O (nm) |
| 最优性 | 不一定全局最优 | 保证全局最优 |
四、算法选择策略
- 优先尝试贪心：若问题满足 “每一步局部最优能推导出全局最优”（如活动选择、哈夫曼编码），优先用贪心，实现简单且效率高；
- 贪心失效用 DP：若局部最优无法得到全局最优（如非规范面额找零、LIS），或问题存在重叠子问题，选择动态规划；
- 特殊场景优化：部分问题（如 LIS）可通过 “贪心 + 二分” 优化动态规划的时间复杂度，兼顾效率与最优性。
五、总结
贪心算法是 “短视的最优”，依赖问题本身的性质；动态规划是 “全局的最优”，通过记录子问题解避免重复计算。二者均基于 “最优子结构”，但贪心更强调 “贪心选择性质”，动态规划更依赖 “子问题重叠性”。
在实际开发中，需先分析问题特性：若能证明贪心选择的正确性，优先使用贪心；若无法证明，或问题存在重叠子问题，则选择动态规划。掌握两种算法的核心思想与适用场景，是解决算法优化问题的关键。
以上所有代码均可直接编译运行，建议结合具体场景调试，深入理解算法的执行过程与核心逻辑。
