K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
现有硬币面额集合为[1, 3, 4]，针对该最少硬币找零问题，以下说法正确的是：
贪心算法总能得到该问题的最优解，比如找零6时，贪心算法会得到最优解
该问题只能通过暴力枚举所有可能的硬币组合求解，无法使用动态规划优化
使用动态规划求解时，初始化dp[0] = 0（表示找零0元需要0枚硬币），对于每个金额i，dp[i] = min(dp[i - coin] + 1) 其中coin遍历所有不大于i的硬币面额，该状态转移方程是正确的
当找零金额为0时，最少需要1枚硬币