一道再经典不过的动规题

我们先接着这道题的过程，梳理一下DP的思路

先来介绍一下什么是动态规划(DP)： 1.本质：一种递推 从前面得到的数值可以推出后面的数值 2.要素： 一是要求题目不需要最优解的过程 二是后面的数值只由前面的数值决定 3.内容： 首先是想好dp要记录什么（一般是题目问的） 其次是初始化数组（尤其注意dp[1]或者dp[0]） 最后要想好状态转移方程，也就是如何转移dp中的数据 这点是最重要的内容

现在看到原题

对于一个n元的凑法，你可以从n-11元开始，再取一枚11元的硬币，也可以从n-5元开始取一枚5元的，也可以从n-1开始取1元的，最后三个结果取最小值即可。

我们现在让dp[i]记录i元的最小硬币数，所以有： dp[i] = min(min(dp[i - 1],dp[i - 5]),dp[i - 11]) + 1;

这就是状态转移方程。

最后附上代码

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1e6 + 5;
int n;
int dp[SIZE];

int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
	{
		if(i < 5) dp[i] = dp[i - 1] + 1;
		if(i >= 5 && i < 11) dp[i] = min(dp[i - 1],dp[i - 5]) + 1;
		if(i >= 11) dp[i] = min(min(dp[i - 1],dp[i - 5]),dp[i - 11]) + 1;
	}
	printf("%d",dp[n]);
	return 0;
}