DP题解

这是一道非常明显的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开始

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,dp[200010]; 
int main(){
    //初始化为最大值，否则取min一定为0
	memset(dp,0x3f,sizeof(dp));
	cin >> n;
    //DP初始化
	dp[1]=1,dp[2]=2,dp[3]=3,dp[4]=4,dp[5]=1,dp[6]=2,dp[7]=3,dp[8]=4,dp[9]=5,dp[10]=2,dp[11]=1;
	for(int i=12;i<=n;i++){//由12开始枚举
		dp[i]=min(dp[i],min(dp[i-1],min(dp[i-5],dp[i-11])))+1;//状态转移
	}
	cout << dp[n]; 
	return 0;
}

至此此题已解

os:求个点赞不过分吧，求你们了