动态规划和贪心算法的决策方式有什么本质区别，为什么贪心在有些最优化问题上失效？

核心机制对比

动态规划的核心是把问题定义为状态，转移方程合并所有可能决策，最终在状态集合中取最优。例如在硬币问题中，dp[i]存储金额i的最小硬币数，每个状态尝试所有面额更新。贪心则不在状态空间搜索，而是按照一个确定性规则每次挑一个硬币，例如面额降序取时可能立即固定选择，不做备选。

贪心之所以快是它把O(n*C)的状态扫描压缩成O(n)或O(m)，但代价是必须验证每一步贪心选择不会妨碍未来。数学上，贪心通常要求一个全序的局部指标，并且该指标的可加性使余下问题独立。若缺少该性质，当前最佳会夺走更优的未来组合。

function greedy(coins, amount) {
  let count = 0;
  let remaining = amount;
  for (let coin of [...coins].sort((a,b)=>b-a)) {
    while (remaining >= coin) {
      remaining -= coin;
      count++;
    }
  }
  return remaining === 0 ? count : -1;
}

function dpCoins(coins, amount) {
  const dp = new Array(amount+1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (let c of coins) {
      if (i-c >= 0) dp[i] = Math.min(dp[i], dp[i-c]+1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

const coins = [1,3,4];
const target = 6;
console.log('greedy:', greedy(coins, target));
console.log('dp:', dpCoins(coins, target));

greedy: 3
dp: 2

一个找零钱反例

设硬币面额为1、3、4，要凑6元。贪心按最大面额优先：先取4，余2只能1+1，总数3枚（4+1+1）。但最优是3+3两枚。这里贪心选择4后，剩余2已无法用3，被迫用1。因为局部最大面额并没有为剩余金额保留更好的公约空间。

对这个例子做动态规划：dp[0]=0，dp[1]=1,dp[2]=2,dp[3]=1,dp[4]=1,dp[5]=2,dp[6]=2。它比较了取4继续到2（3枚）和取3到3（2枚）。可见只有枚举状态才能识别3+3比4+1+1更优。贪心一次决定无缘比较分支。

何时贪心有效与判断

贪心有效需要两个条件：一是问题具有最优子结构（全局最优包含局部最优子问题最优）；二是贪心选择性质，即存在一种排序或规则使每次的选择都是最优前缀。典型如活动选择：按结束时间排序，最早结束的活动是对所有最优解都有益的选择。如果排序规则没有这一数学保证，立即失效，例如分数背包可贪心但0-1背包不能。

工程师判断时可以采取两个步骤：先尝试将决策表达式写成递归最优化，再对每种排序规则做交换论证，证明交换任意两个选择不会变差。更实用的是在真实规模内跑随机数据生成，把贪心结果与穷举或DP解对比，若存在差例则放弃贪心。但测试只能证伪不能证实，缺少证明时安全选择动态规划。

容易答错的地方

贪心问题都能用动态规划解决

并非所有贪心问题都适合用动态规划高效求解。DP依赖可枚举的状态和可记忆化的子问题；部分贪心问题虽可能写出递推式，但状态空间可能呈指数级或缺乏重叠子问题，例如哈夫曼编码若强行定义区间或子集型状态，计算量远大于贪心策略。因此不能无条件断言所有贪心问题都能用DP解决。

贪心失效是因为没有最优子结构

贪心失效往往不是缺少最优子结构。找零面额1,3,4时金额6的最优解包含金额3的最优解（1枚3），故最优子结构满足，但局部选4不是全局最优的一部分。失败点是贪心选择性质不成立。

面试官还会怎么问？

把知识连起来