• 给定数量无限的面值分别为 x1, x2, . . . , xn 的硬币，我们希望将金额 v 兑换成零钱，即希望找 出一堆总值恰好为 v 的硬币。这有时候是不可能的。例如，如果硬币只有 5 和 10 两种面值， 则可以兑换 15 却不可以兑换 12. 请设计一个 O(nv) 的动态规划算法，判断能否兑换金额 v。 1 图 1: 最长子序列问题的扩展. • 考虑上述零钱兑换问题的一个变体：有面值 x1, x2, . . . , xn 的硬币，希望兑换的价格为 v，但是 每种面值的硬币最多只能使用一次。举例来说，如果硬币面值为 1、5、10、20，则可以兑换的 价格包括 16=1+15 和 31=1+10+20，但是无法兑换 40（因为 20 不能用两次）。请设计一个 O(nv) 的动态规划算法判断能否兑换金额 v。 • 考虑上述零钱兑换问题的另一个变体：给定无限多的面值 x1, x2, . . . , xn 的硬币，我们希望用 其中最多 k 枚硬币兑换价格 v，即需要找到不超过 k 枚的硬币，使其总面值为 v。这也可能是 无法实现的。例如，若面值为 5 和 10，k=6，则可以兑换 55，但却不能兑换 65. 请设计一个 动态规划算法判断能否兑换金额 v。

对于第一个问题，我们可以设计一个动态规划算法来解决。我们定义状态 dp[i] 表示金额 i 能否被兑换成硬币的组合，初始值 dp[0] 为 true，其余为 false。对于每个硬币面值 xj，我们可以转移状态 dp[i]，如果 i >= xj 且 dp[i-xj] 为 true，则 dp[i] 也为 true。最终，如果 dp[v] 为 true，则说明金额 v 可以被兑换成硬币的组合。

对于第二个问题，我们可以将上述动态规划算法进行稍微修改。我们定义状态 dp[i][j] 表示使用前 j 种硬币是否可以兑换金额 i，初始值 dp[0][j] 为 true，其余为 false。对于每个硬币面值 xj，我们可以转移状态 dp[i][j]，如果 i >= xj 且 dp[i-xj][j-1] 为 true，则 dp[i][j] 也为 true。最终，如果 dp[v][n] 为 true，则说明金额 v 可以被兑换成硬币的组合，且每种面值的硬币最多只能使用一次。

对于第三个问题，我们可以定义状态 dp[i][j] 表示使用最多 j 枚硬币是否可以兑换金额 i，初始值 dp[0][j] 为 true，其余为 false。对于每个硬币面值 xj，我们可以转移状态 dp[i][j]，如果 i >= xj 且 dp[i-xj][j-1] 为 true，则 dp[i][j] 也为 true。最终，如果 dp[v][k] 为 true，则说明使用最多 k 枚硬币可以兑换金额 v。