关于贪心与递推的区别，说法错误的是（ ）

1. 贪心算法（Greedy Algorithm）

   • 核心思想： 在每一步决策时，都选择当前看起来最佳（或最优）的方案，不考虑未来的影响，希望通过局部最优的选择达到全局最优。
   • 特点：
     • 局部最优： 每一步只关注当前，做出当下最好的选择。
     • 不回溯： 一旦做出选择，就不会再更改。
     • 不一定得到全局最优： 很多时候，局部的最优选择并不能保证最终得到全局的最优解。只有当问题具有“贪心选择性质”（即局部最优解能够导出全局最优解）时，贪心算法才能得到最优解。
     • 实现简单： 通常比动态规划更直观和容易实现。

2. 动态规划（Dynamic Programming，递推）

   • 核心思想： 将一个复杂的问题分解成若干个相互重叠的子问题，通过解决这些子问题并存储它们的解（避免重复计算），从而逐步推导出原问题的解。它通常通过定义一个“递推关系式”或“状态转移方程”来描述子问题之间的依赖关系。
   • 特点：
     • 最优子结构： 原问题的最优解包含其子问题的最优解。
     • 重叠子问题： 解决问题的过程中，会多次遇到相同的子问题。
     • 保证得到全局最优： 如果一个问题适用于动态规划（即满足最优子结构和重叠子问题性质），并且动态规划算法正确实现，那么它一定能找到全局最优解。
     • 通常比贪心复杂： 需要定义状态和递推关系，实现上可能比贪心算法更复杂。

现在我们来分析题目中的各个选项：

• A. 贪心法推进每一步不依据某一固定的递推式。

  • 解析： 贪心算法在每一步是根据当前的“最佳”标准直接做出选择，并不像动态规划那样，需要建立一个严密的数学递推关系式来一步步求解子问题。它更像是一种“直觉式”的局部决策。所以此说法是正确的。

• B. 贪心推进是当前看似最佳的贪心决策。

  • 解析： 这正是贪心算法的定义和核心思想。贪心算法在每一步都选择当前看起来最优的决策，而不考虑之后可能产生的后果。所以此说法是正确的。

• C. 贪心不一定能得到最优解。

  • 解析： 这是贪心算法的常见局限性。只有当问题满足特定的性质（如贪心选择性质）时，贪心算法才能得到最优解。对于很多问题而言，贪心算法只能给出次优解。例如，在某些找零钱问题中，贪心算法（每次找最大面额的）不一定能用最少硬币完成找零。所以此说法是正确的。

• D. 递推不一定能得到最优解。

  • 解析： “递推”在此语境下指的是动态规划。动态规划的核心目的和优势之一就是，如果一个问题具备最优子结构和重叠子问题特性，并且能够用动态规划方法解决，那么正确实现的动态规划算法一定能够找到问题的全局最优解。它通过系统地探索所有可能的子问题组合并选择最优路径来实现最优解。因此，说动态规划“不一定能得到最优解”是错误的。