发帖
雷达卡
贪心算法（greedy algorithm）是一种用于解决具有最优子结构特征的优化问题的有效方法。该算法的核心在于准确识别问题是否具备以下三个关键性质：贪心选择性质、最优子结构性质以及无后效性。
首先，贪心选择性质意味着可以通过一系列局部最优的选择来构造全局最优解。也就是说，在每一步决策中都选择当前看起来最优的方案，最终能够得到整体最优的结果。这种“当下最优”的策略是贪心算法区别于其他算法的重要特点。需要注意的是，并非所有问题都能通过这种方式获得最优解，因此在使用前必须严格证明该问题满足贪心选择的前提条件。通常可以借助数学归纳法来进行验证。从实现角度看，贪心算法的代码逻辑较为简洁，常见做法是用一个 flag[] 数组记录元素是否被选中，重点难点在于对性质的识别与判断。
其次，最优子结构性质指的是：一个问题的最优解包含其子问题的最优解。换句话说，每一阶段的最优决策组合起来仍构成全局最优。这一性质保证了“步步最优”可以导向“总体最优”。正因为如此，贪心算法能够在每个状态上仅依据当前信息做出决定，而无需回溯或重新评估之前的步骤。
最后，无后效性是指某一状态一旦确定，后续的决策不会受到此前路径的影响，未来的状态仅依赖于当前状态。这一点类似于高中数学中提到的马尔科夫链思想。正是由于这一特性，使得局部最优解能够顺利拼接为全局最优解，而不必担心历史决策带来的干扰。
贪心算法在实际中有广泛的应用场景，例如01背包问题中的部分情况、活动安排问题、资源分配调度、分发糖果等问题。对于学习者而言，备考时应重点关注如何识别贪心特征。一旦确认可用贪心策略求解，编写代码往往顺理成章。考试中若能识别出贪心模型，往往是提分的关键机会。
[此处为图片1]
动态规划
以斐波那契数列的求解为例引入动态规划的思想。此前我们分析过斐波那契递归树，可以发现 fib(1)、fib(2) 等子问题被重复计算多次。这揭示了一个普遍现象：在递归和分治过程中，常常会出现子问题重叠的情况。为避免重复计算，提高效率，我们可以采用动态数组 dp 来存储每一个已计算的子问题结果。这种方法即被称为动态规划（Dynamic Programming）。
动态规划的基本求解步骤包括：
- 分析最优解的性质，并明确其结构特征；
- 递归地定义最优值的表达形式；
- 采用自底向上的方式逐步计算最优值；
- 根据计算过程中保存的信息，重构出完整的最优解。
动态规划的三大基本要素为：最优子结构性质、无后效性以及子问题重叠性质。
其中，最优子结构性质表示原问题的最优解中所包含的各个子问题的解也必定是最优的；无后效性则说明某个状态一旦确定，其后续发展仅取决于当前状态，而不受达到该状态的具体路径影响；而子问题重叠性质是指在多阶段决策过程中，同一子问题可能被多次调用。动态规划正是利用这一特性，将每个子问题的解保存在表格中，下次需要时直接查表获取，从而显著提升效率。如果问题不具备子问题重叠性，则动态规划的优势将不复存在。
掌握动态规划的关键在于理解并构建正确的状态转移方程。建议通过大量练习加以巩固，特别是经典题目如最长公共子序列、PPT中的典型例题等。这些题目有助于深入理解状态设计与转移逻辑。
[此处为图片2]
本课程内容较为灵活，算法思维的培养难以依靠短期突击达成高分目标。建议同学们重视平时对基础算法思想的理解与积累，熟练掌握常见算法的实现方式。对于追求高绩点的学生来说，需深入理解各类算法适用场景；而对于希望顺利通过考试的同学，则应至少掌握基本概念和简单编程思路。真正的提升来源于持续的学习与实践。
京公网安备 11010802022788号
