首页 > 代码库 > HDU 1284 钱币兑换问题

HDU 1284 钱币兑换问题

动态转移方程:dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

即要想兑够 i,有三种方法:

1.从 i - 1 再增加一个1分的;

2.从 i - 2 再增加一个2分的;

3.从 i - 3 再增加一个3分的。

两个 for 循环:

i :1-->3

i = 1 表示只用1分的兑法,i = 2 表示用1分的和2分的兑法,i = 3 表示全用上的兑法。

j:1-->n

从小到大依次求出兑够 j 的兑法

代码如下:

#include <iostream>#include<cstdio>#include<cstring>using namespace std;const int M = 32768 + 10;int dp[M];int main(){    int n;    memset(dp, 0, sizeof(dp));    dp[0] = 1;    for (int i = 1; i <= 3; i++)    {        for (int j = 1; j <= 32767; j++)        {            dp[j] += dp[j - i];        }    }    while (~scanf("%d", &n))    {        printf("%d\n", dp[n]);    }    return 0;}