请设计并实现一个动态规划解法来解决一个你遇到过的最典型的动态规划问题，并解释你为什么一开始会误判为贪心算法。

Question

Accepted Answer

考察点：考察动态规划建模能力与算法识别能力。回答思路：正确识别问题的最优子结构和重叠子问题 清晰阐述动态规划的转移方程和边界条件 对比贪心算法与动态规划的区别，说明误判原因 给出复杂度分析和可能的优化

考察说明