dp[i-1] 再拿 1 张 1 元钞票，则是 i 元，因此：dp[i] = dp[i-1] + 1; dp[i-5] 再拿 1 张 5 元钞票，则是 i 元，因此：dp[i] = dp[i-5] + 1; dp[i-11] 再拿 1 张 11 元钞票，则是 i 元，因此：dp[i] = dp[i-11] + 1; 题目要求最少的组合张数，所以只需要对 dp[i-1]+1, dp[i-5]+1, dp[i-11]+1 取最小即可。 状态转移方程：dp[i] = min{ dp[i-1]+1, dp[i-2]+1, dp[i-11]+1 };

首先理解题目，我们知道这道题是线性DP的标准题。ok， 正解开始： 因为每次都要判断是不是要加1元，5元还是11元，我们先把所有数初始化为1，之后就是判断：（i>=5还是i>=11） i>=5状态转移方程:min(dp[i],dp[i-5]+1) i>=11时:min(dp[i],dp[i-11]+1)。 这就是这题的解题思路。 上代码：

本人仅知在 0 <= n <= 2000 0000 的范围内 此题解有效 此代码看上去很简单 只是在传统贪心上加入两个特判罢了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

几百年前就写完了，但是当时没想要写题解。现在我也看不出是什么思路了，凑合着看吧。 要注意有得时候他并不是贪心，比如15时不是一张11+4张1，而是3张5。所以要多考虑一些情况

我是乐子，又来发题解了 大佬给几个赞吧。

不难发现， 其实dp就是状态转移公式+循环

本片为上古时期的代码 先从最暴力的思路讲起，枚举 11 张 iii 个，5张 jjj个，1张 kkk 个，时间复杂度为 O(n3)O(n^3)O(n3) 注意到：1张完全可以通过数学方法算出来 (k=n−11×i−5×j)(k = n-11\times i-5\times j)(k=n−11×i−5×j) ， 时间复杂度为 O(n2)O(n^2)O(n2) 还能在优化吗？肯定的 注意到正解所用的 kkk 均小于 5 ，而 15=11+1×4=5×315 = 11+1\times 4 = 5\times 315=11+1×4=5×3 是小数据唯一不符合贪心的返例，因此 iii 一定大于 max⁡(n/11−3,0)\max(n/11-3,0)max(n/11−3,0) 这样，时间复杂度为 O(n)O(n)O(n) 但我们还能据需优化 如果我们知道 iii 多大，可以求出剩下，而剩下一定 i<5i<5i<5 即 j=floor((n−11×i)/5)j = floor((n-11\times i)/5)j=floor((n−11×i)/5) 时间复杂度就是 O(1)O(1)O(1) 级别 代码: 循环运行次数是 3×7=213\times 7 = 213×7=21 次

这是一道非常明显的DP题 为什么它是DP呢？ 先举几个例子 当n=1时，ans=1×1 当n=2时，ans=1×2 当n=3时，ans=1×3 当n=4时，ans=1×4 当n=5时，ans=5×1 当n=6时，ans=1×1+5×1 当n=7时，ans=1×2+5×1 当n=8时，ans=1×3+5×1 当n=9时，ans=1×4+5×1 当n=10时，ans=5×2 当n=11时，ans=11×1 当n=12时，ans=11×1+1×1 ...... 总结一下： 此题中，对于所有n，n一定能够拆分成 1×a+5×b+11×c 的形式 即 n=1×a+5×b+11×c (n,a,b,c>=0) 所以，此题解体思路就出来了 令 dp[i]为凑出i块钱最少需要多少张钞票 则 dp[i]可由i-1&i-5&i-11凑出 状态转移方程：min(dp[i-1],dp[i-5],dp[i-11]) 但是当i<12时，i-11<0 会造成越界 所以将dp[1]-dp[11]初始化 状态转移的循环从12开始 代码如下 至此此题已解 os:求个点赞不过分吧，求你们了