换零钱
换零钱
输入1个数N，N = 100表示1元钱。(1 <= N <= 100000)
Output
输出Mod 10^9 + 7的结果
Input 示例
5
Output 示例
4
这是一道动态规划题，这一题让我彻底感觉到自己的弱小，提交18次吧，才对，递推公式，我差不多推了一个下午，到最后，我都不知道自己在干什么了，我还想和别人组队组队，自己负责动态规划这部分，这不是要坑吗？
废话不说那么多了，说说这道题吧，题目已经贴出来了
我们用个二维数组d[i][j]表示i元钱用不大于coin[j]的面值组成的种类数
dp[i][j]=dp[i][j-1]+dp[i-coin[j]][j];
注意下初始化
代码如下
#include
#include
#include
using namespace std;
#define MAXN 100008
#define Mod 1000000007
int dp[MAXN][15];
int main()
{__int64 coin[15]={0,1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};__int64 N,i,j;cin>>N;for(i=1;i<=13;i++){dp[1][i]=1;}for(i=1;i<=N;i++)dp[i][1]=1;for(i=2;i<=N;i++)for(j=1;j<=13;j++){if(i>=coin[j])dp[i][j]=max(dp[i-coin[j]][j],1)+dp[i][j-1];else dp[i][j]=dp[i][j-1];dp[i][j]=dp[i][j]%Mod;}printf("%d\n",dp[N][13]);}
很菜；做完后，有学习下别人的代码，如下
#include
#include
#include
#include
#include
#include
using namespace std;int ans[100001] = {0};
const int mod = 1000000007;
int main()
{int money[] = {1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};int n = sizeof(money)/sizeof(int);int total;cin>>total;ans[0] = 1;for(int i=0; i 我是这样理解的，似乎超级走楼梯似的，只怪我当时没听别人的，不相信这是对的，所以悲剧了一下午，今天明白一个道理：该感谢的人一定要感谢
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！