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)。 这就是这题的解题思路。 上代码：

几百年前就写完了，但是当时没想要写题解。现在我也看不出是什么思路了，凑合着看吧。 要注意有得时候他并不是贪心，比如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 次