没错，这就是难度Medium的换硬币。

每日一题翻到的，上次提交还是2015年。

刚看到满脸不屑，这不是教科书般的贪心么，吃着面包两三行代码搞定。

果断WA了。

看看case想了想，嗯，RMB可以贪心是因为有一块钱兜底，怎么贪心都能兜回来；这个题奇奇怪怪的case，很容易出现贪心了凑不出来的情况。

そうですね

暴力搜索肯定不行，看看15年的一大排TLE就知道了。

这个难不倒我，暴力搜索不行那带剪枝试试。于是我按照余数的循环对每一个硬币数量做了个基于贪心的剪枝。

。。。。。。然后发现这个剪枝，手滑会触发很多corner case不说，会剪掉正确的case。。。。！！

生无可恋了

。。。。。。

翻了翻题目，amount有上界，那就只剩下带状态的搜索/动规方法了。

于是我灵光一现，写出了个二维的状态方程。

。。。。。。

虽然直觉上感觉不对，但还是沉没成本+侥幸心理，在本地砍掉无用运算+预计算，把时间大约砍掉了一小半。

。。。。。。还是TLE了

瘫在椅子上，仔细一想，这。。。特么就就是个一维状态的动规啊，吐血了。。。。。。

翻了翻15年提交的代码，发现心路历程和这次是差不多的，一声叹息。

代码我都不好意思贴，黑历史啊黑历史：（

——此处是内容的分割线——

除非注明，否则均为广陌原创文章，转载必须以链接形式标明本文链接

本文链接：https://www.utopiafar.com/2022/05/21/finally_got_an_ac_after_7_years/

码字不易，如果觉得内容有帮助，欢迎留言or点赞！