证明找零钱问题具有最优子结构性质
时间: 2023-10-10 18:09:15 浏览: 182
动态规划之找零钱问题
找零钱问题的最优子结构性质可以通过以下方式证明:
假设我们需要找零金额为n的硬币,假设我们有一组硬币面值{c1, c2, c3, ..., ck}可供使用。那么,我们可以将问题分解为两个子问题:
1. 找零金额为n-ci的硬币,其中ci是一组硬币面值中的某一个硬币。
2. 找零金额为n的硬币,但我们不使用硬币面值为ci的硬币。
这两个子问题都是找零钱问题,而且它们都是原问题的子问题。如果我们能够分别解决这两个子问题,那么我们就可以得到原问题的最优解。
因此,我们可以得出结论:找零钱问题具有最优子结构性质。
阅读全文