昨天写的分析不太对,重发一下。这道题是要用动态规划的, dp[i]=min j {dp[i-j]+1}。这道题一般是不能用贪心的,第一种情况可以用贪心只是因为可供找零的面值很特殊,但是它的证明我也不会。总之只是可供找零的面值满足某个条件的时候,贪心算法恰好能得到最优解
点赞 1

相关推荐

牛客网
牛客企业服务