动态规划之钱币兑换问题

钱币兑换问题

在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

Input

每行只有一个正整数N，N小于32768。

Output

对应每个输入，输出兑换方法数。

Sample Input

2934
12553

Sample Output

718831
13137761

先看代码，着重看以下递推式的循环

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = (int) 1e9+7;
const int MAXN = 32767+10;

LL dp[MAXN];
int main()
{
    int n;
    const int m = 3;
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    //dp[1] = 1;    // 不能写这一步
    for( int i=1; i<=m; i++ )
    {
        for( int j=i; j<=MAXN; j++ )
            dp[j] = max(dp[j], dp[j] + dp[j-i]);
    }
    while( scanf("%d", &n) != EOF )
    {
        printf("%d\n", dp[n]);
    }

    return 0;
}

递推式循环哪里外层从1到3，代表三种硬币，同时这三种硬币的价值等于他们的序号。内层j代表的是j分钱，从i开始，为什么是从i开始呢？

这是因为j代表的是钱数，不能小于当前价值为i的硬币。

现在我们来简单模一下这个循环

i = 1时你会发现从dp[1] 到 dp[MAXN] 都是 1，没错，就是这样。这是因为i = 1时代表只能选1分的硬币，自然只有一种。

那么i = 2时这时dp数组就是递增的了，这是因为当前已经可以选2了，当然是钱数越多，种类数越多了。

然后及时 i = 3了，这是同 i= 2一样，dp数组继续递增，至于为什么，这样算就能得到正确答案。

我们来举个例子

比如需要用这三种硬币来凑够5分钱，那么有几种方法呢？

首先模拟一下递推你会发现dp[5] 经过这几次运算。

i = 1时 dp[5] = 1;

i = 2时 dp[5] = dp[5] + dp[3] = 1 + 2 = 3;

i = 3时 dp[5] = dp[5] + dp[2] = 3 + 2 = 5; 其中dp[2] and dp[3] 也在因为递推而值改变，所以就有前面的模拟结果。

正好 5 有 1 1 1 1 1， 2 1 1 1， 2 2 1， 3 1 1 ， 3 2 这五种。

那么来分析一下

首先 1 1 1 1 1 这样肯定是一种了，这样正好对应 i = 1的情况。然后 2 1 1 1 和 2 2 1又是两种。对应于当 i = 2 时此时还是dp[5] = dp[5] + dp[3]; 加上dp[5]是因为dp[5] 是之前的已经知道的种数，dp[3] 则是因为当前为选的是2分的硬币，所以选上一个2，那么还剩3个1，三个一组和的种数就是dp[3], 接着你会发现dp[3]能由1分和2分的硬币组成的种类数在dp[5]之前已经计算过了，所以直接哪来用就好了。

最后就是 i = 3的情况了，大致同i = 2 的想法一样。 5 除去一个3就是 2，剩下的2分钱可组成种数dp[2]已经不能用3分的硬币来增加了，此外dp[2]在之前的递推中也已经计算过了。就这样。

总的来说动态规划还是要多想，多做练习。