本文主要是介绍674 - Coin Change，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一道很水的DP，但我做的时候也很费劲，由于存在面值为1的时候，所以所有面额都至少有1种方法。
推导出状态方程就是 dp(V,step) += dp(V - i * coin[step],step - 1); 其中V为当前的面值，coin[step]为硬币的面额，递归边界，如果step == 0（也就是递归到硬币面额为1的时候，返回1);
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<string>
#include<sstream>
#include<ctime>
using namespace std;
#define _PI acos(-1.0)
#define INF 1 << 30
#define esp 1e-6
typedef long long LL;
typedef unsigned long long ULL;
/*===============================================*/
#define MAXD 7489 + 10
int _dp[5][MAXD];
const int coin[] = {1,5,10,25,50};
int dp(int step,int V){if(!step)return _dp[step][V] = 1;if(_dp[step][V] > 0)return _dp[step][V];_dp[step][V] = 0;for(int i = 0 ; i * coin[step] <= V ; i++)_dp[step][V] += dp(step - 1,V - i * coin[step]);return _dp[step][V];
}
int main(){int n;memset(_dp,-1,sizeof(_dp));while(scanf("%d",&n) != EOF){int ans = dp(4,n);printf("%d\n",ans);}return 0;
}
这篇关于674 - Coin Change的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
