特性维度贪心算法 (Greedy Algorithm)动态规划 (Dynamic Programming, DP)核心思想每一步都做出在当前状态下局部最优的选择期望以此达到全局最优 。将复杂问题分解为重叠子问题通过保存子问题的解记忆化来避免重复计算最终得到全局最优解 。最优性保证不一定能保证得到全局最优解仅在问题具有“贪心选择性质”和“最优子结构”时才可保证 。可以保证得到全局最优解前提是问题具有“最优子结构”和“重叠子问题” 。求解方向通常是自顶向下的每一步做出选择后问题规模减小。通常是自底向上的从最小的子问题开始逐步构建到原问题也可用带记忆化的递归实现自顶向下。效率时间复杂度通常较低因为每步选择后问题规模减小常为O(n)或O(n log n)。时间复杂度通常较高因为需要求解所有相关子问题常为O(n * m)等多项式时间 。空间复杂度通常为O(1)仅需常数空间记录当前状态。通常需要额外的存储空间数组、表来记录子问题的解空间复杂度常为O(n)或O(n * m)。典型应用霍夫曼编码、最小生成树Prim, Kruskal、单源最短路径Dijkstra权值非负时、活动选择问题。背包问题、最短路径问题Floyd-Warshall、最长公共子序列、编辑距离、硬币找零最少硬币数。关键差异与联系最优子结构两者都要求问题具有最优子结构即一个问题的最优解包含其子问题的最优解 。贪心选择性质 vs 重叠子问题贪心算法额外要求问题具有贪心选择性质即通过局部最优选择能直接导向全局最优解无需考虑其他子问题的解 。动态规划则要求问题具有重叠子问题即递归算法会反复求解相同的子问题因此需要记忆化来提升效率 。决策范围贪心算法每步决策时只考虑当前状态不回退。动态规划在决策时会考虑所有可能的子问题解并进行比较选择。经典问题对比硬币找零最少硬币数这个问题能清晰展示两者差异。假设硬币面额为coins [1, 3, 4]需要凑出总金额amount 6。1. 贪心算法解法可能非最优贪心策略每次选择面额最大且不超过剩余金额的硬币。#include iostream #include vector #include algorithm using namespace std; int coinChangeGreedy(vectorint coins, int amount) { sort(coins.rbegin(), coins.rend()); // 降序排列方便从最大面额开始 int count 0; for (int coin : coins) { while (amount coin) { amount - coin; count; } } return amount 0 ? count : -1; // 如果最后amount不为0说明无法凑出 } int main() { vectorint coins {1, 3, 4}; int amount 6; int result coinChangeGreedy(coins, amount); cout 贪心算法所需硬币数: result endl; // 输出: 3 (对应方案: 4 1 1) // 但实际上最优解是 2 (3 3) return 0; }说明对于coins [1, 3,4],amount 6贪心算法选择了4 1 1共3枚硬币但最优解是3 3共2枚。这说明此问题不满足贪心选择性质贪心算法不能保证最优 。2. 动态规划解法保证最优定义dp[i]为凑出金额i所需的最少硬币数。#include iostream #include vector #include algorithm #include climits using namespace std; int coinChangeDP(vectorint coins, int amount) { // dp[i] 表示凑出金额 i 所需的最少硬币数初始化为一个较大值如 amount1 或 INT_MAX vectorint dp(amount 1, amount 1); dp[0] 0; // 金额为0时不需要任何硬币 for (int i 1; i amount; i) { for (int coin : coins) { if (coin i) { // 状态转移方程dp[i] min(dp[i], dp[i - coin] 1) dp[i] min(dp[i], dp[i - coin] 1); } } } // 如果 dp[amount] 未被更新说明无法凑出 return dp[amount] amount ? -1 : dp[amount]; } int main() { vectorint coins {1, 3, 4}; int amount 6; int result coinChangeDP(coins, amount); cout 动态规划所需最少硬币数: result endl; // 输出: 2 (对应最优方案: 3 3) return 0; }说明动态规划通过计算并比较所有可能的选择dp[i] min(dp[i], dp[i - coin] 1)确保了最终解dp[amount]是全局最优的 。另一个例子股票买卖的最佳时机 II (LeetCode 122)这个问题展示了贪心算法有效且更简洁的场景。问题描述给定股票每天的价格你可以进行多次交易买一次卖一次算一次交易但必须在再次购买前出售掉之前的股票。求最大利润。1. 贪心算法解法贪心策略分解利润。将整体利润分解为每天的利润差只收集所有正利润。#include iostream #include vector using namespace std; int maxProfitGreedy(vectorint prices) { int profit 0; for (int i 1; i prices.size(); i) { // 如果今天价格比昨天高就把这部分利润加上 int diff prices[i] - prices[i - 1]; if (diff 0) { profit diff; } } return profit; } int main() { vectorint prices {7, 1, 5, 3, 6, 4}; cout 贪心算法最大利润: maxProfitGreedy(prices) endl; // 输出: 7 (解释: 1买5卖, 3买6卖) return 0; }说明该问题中将利润分解为每日决策后局部最优每天有正利润就交易能直接累加成全局最优。贪心算法高效且正确 。2. 动态规划解法定义dp[i][0]表示第i天结束时不持有股票的最大利润dp[i][1]表示第i天结束时持有股票的最大利润。#include iostream #include vector #include algorithm using namespace std; int maxProfitDP(vectorint prices) { int n prices.size(); if (n 2) return 0; vectorvectorint dp(n, vectorint(2, 0)); dp[0][0] 0; // 第一天不持有 dp[0][1] -prices[0]; // 第一天持有即第一天买入 for (int i 1; i n; i) { // 第i天不持有要么是昨天就不持有要么是昨天持有今天卖出 dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]); // 第i天持有要么是昨天就持有要么是昨天不持有今天买入注意可以多次交易 dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i]); } // 最后一天不持有股票的状态就是最大利润 return dp[n-1][0]; } int main() { vectorint prices {7, 1, 5, 3, 6, 4}; cout 动态规划最大利润: maxProfitDP(prices) endl; // 输出: 7 return 0; }说明动态规划同样可以解决该问题它清晰地刻画了每天两种状态下的最优决策。但相比贪心解法DP 需要更多的空间 (O(n)) 和稍复杂的逻辑 。总结与选择依据场景推荐算法理由问题具有贪心选择性质且只需一个最优解值。贪心算法实现简单、运行高效、空间占用少 。问题不具有贪心选择性质或需要得到具体的解路径。动态规划能保证全局最优适用于更广泛的最优化问题 。问题具有重叠子问题和最优子结构且子问题数量有限。动态规划通过记忆化避免重复计算效率优于暴力递归。需要对比所有可能选择的结果时。动态规划DP 的状态转移天然涵盖了比较过程。在实际编程中尤其是算法竞赛或面试中识别问题特性是关键。可以先尝试判断问题是否具有贪心选择性质通常需要证明或举反例若无法证明或存在反例如上述硬币找零问题则应转向动态规划思路。动态规划虽然设计起来更复杂但其通用性更强是解决最优化问题的强大工具 。参考来源理解动态规划算法与贪心算法区别----找钱问题最少钱币数凑硬币详解-2-动态规划算法初窥-编程练习题100leetcode 贪心_贪心算法买卖股票的最佳时机II《剑指offer》—— 剪绳子动态规划贪心算法最少钱币数凑硬币详解-2-动态规划算法初窥-编程练习题100最少硬币找零问题-动态规划