描述
我们知道人民币有1、2、5、10、20、50、100这几种面值。
现在给你n(1≤n≤250)元，让你计算换成用上面这些面额表示且总数不超过100张，共有几种。
比如4元，能用4张1元、2张1元和1张2元、2张2元，三种表示方法。
输入
输入有多组，每组一行，为一个整合n。
输入以0结束。
输出
输出该面额有几种表示方法。
样例输入
1
4
0
样例输出
1
3


想半天不知道用DP怎么写，求代码一定要带上注释啊。。。
              最近学的有的郁闷，卡了一天，希望能有人指点一下。

动态规划不会，穷举法的有一个
#include<stdio.h>
#include<malloc.h>
#include<math.h>

int A[7] = {1, 2, 5, 10, 20, 50, 100};
int count = 0;

void dfs(int n, int top, int s);

int main()
{
    int n;
   
    scanf("%d", &n);
    while (n != 0)
    {
        count = 0;
        dfs(n, 6, 0);
        printf("%d\n", count);
        scanf("%d", &n);
    }
   
    return 0;
}

void dfs(int n, int top, int s)
{
    int i;
   
    if (n == 0)
    {
        count++;
        return ;
    }
    if (top < 0)
        return ;
   
    dfs(n, top-1, s); //先不用A[top]这种货币看看
    for (i=A[top]; i<=n; i+=A[top])
    {
        if (s == 100)//总数不超过100张
            return ;
        dfs(n-i, top-1, ++s);
    }
}

[ 本帖最后由 巧若拙 于 2014-12-3 07:44 编辑 ]

。。继续求大神

发代码上来先看着。如果实在看不懂，改天有时间我再做解释。

#include <stdio.h>

int cal(int n)
{
    const int a[] = {1, 2, 5, 10, 20, 50, 100};
    int f[101][256] = {1};
    int i, j, k;

    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    for(j = 1; j <= 100; j++)
    for(k = a[i]; k <= n; k++)
        f[j][k] += f[j - 1][k - a[i]];

    for(k = 0, i = 1; i <= 100; k += f[i++][n]);
    return k;
}

int main()
{
    int n;
    for(; scanf("%d", &n) != EOF; printf("%d\n", cal(n)));
    return 0;
}

虽然还不是很理解动态规划，但依然斗胆献丑，把自己对楼上代码的理解贴出来，并增加一点点自己的看法。顺便问一句，这个算法的思路是不是和Floyd 算法有点相似？

int cal(int n)
{
    const int a[] = {1, 2, 5, 10, 20, 50, 100};
    int f[101][256] = {1};//f[m][n]的含义为用m张钞票构成的金额为n的组合数量 
    int i, j, k, min, max;

    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)//钞票面值 
    {
        for(j = 1; j <= 100; j++)//钞票张数 
        {
            min = (j > a[i]) ? j : a[i]; //为避免无效运算，给k值规定一个上限和下限 
            max = (n <= j * a[i]) ? n : j * a[i];
            for(k = min; k <= max; k++)//金额总数 
            {
                f[j][k] += f[j - 1][k - a[i]];//该组合中含有一张面值为a[i]的钞票
            }
        }    
    }
    
    for(k = 0, i = 1; i <= 100; k += f[i++][n]);
    
    return k;
}

为了理解这个问题，特意去看了看有关动态规划算法相关文章，里面一句话印象深刻：动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。
1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

找钱问题的子问题从小到大依次是利用面值为a[i]的钞票，计算金额为k时需要j张钞票的组合数量，这里的a[i]，k和j都是从小到大，因为规模较大时可以利用小规模问题计算的结果，反之则不行。a[i]，k和j构成三层循环，a[i]一定要在最外层，k和j的顺序可互换。算法思路有些类似Floyd 算法。
根据上述理解，我写了一个和beyondyf提供的算法相似的代码，只不过k和j的位置换了一下。
初次接触动态规划，理解可能有些不当，请大牛们指正。

int cal_2(int n)
{
    const int a[] = {1, 2, 5, 10, 20, 50, 100};
    int f[256][101] = {1};//f[n][m]的含义为用m张钞票构成的金额为n的组合数量 
    int i, j, k, max;

    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)//钞票面值 
    {
        for(k = a[i]; k <= n; k++)//金额总数 
        {
            max = (k < 100) ? k : 100;
            for(j = 1; j <= max; j++)//钞票张数 
                f[k][j] += f[k-a[i]][j-1];//该组合中含有一张面值为a[i]的钞票
        }
    }
        
    k = 0;
    for(i=1; i<=100; i++)
        k += f[n][i];

    return k;
}

学习

最近比较忙，3天没来论坛，看到大家回复，先结帖 在好好理解一下

你的注释很棒，否则根本看不懂版主大人的回复。我再加一个我自己的理解吧。

f[k][j] += f[k-a[i]][j-1];  //这里是最关键的，也是动态规划的核心，
下面是我调试理解这个程序的时候，打印出来的结果。我分析之后才明白，
比如 f[2][1]+=f[1][0]]=0   表示当子问题为金额2元时，用1张纸币如何获得最优解
因为之前已经包含了一张a[i]元的纸币，这里a[i]=1，所以这个子问题的最优解就是，去掉
a[i]元钱(1元钱)和去掉a[i]元钱的容量(即一张)的最优解。。 
从小规模循环至答案。

4
f[1][1]+=f[1-a[0]][1-1]]=1
f[1][1]+=f[0][0]]=1
f[2][1]+=f[2-a[0]][1-1]]=0
f[2][1]+=f[1][0]]=0
f[2][2]+=f[2-a[0]][2-1]]=1
f[2][2]+=f[1][1]]=1
f[3][1]+=f[3-a[0]][1-1]]=0
f[3][1]+=f[2][0]]=0
f[3][2]+=f[3-a[0]][2-1]]=0
f[3][2]+=f[2][1]]=0
f[3][3]+=f[3-a[0]][3-1]]=1
f[3][3]+=f[2][2]]=1
f[4][1]+=f[4-a[0]][1-1]]=0
f[4][1]+=f[3][0]]=0
f[4][2]+=f[4-a[0]][2-1]]=0
f[4][2]+=f[3][1]]=0
f[4][3]+=f[4-a[0]][3-1]]=0
f[4][3]+=f[3][2]]=0
f[4][4]+=f[4-a[0]][4-1]]=1
f[4][4]+=f[3][3]]=1
f[2][1]+=f[2-a[1]][1-1]]=1
f[2][1]+=f[0][0]]=1
f[2][2]+=f[2-a[1]][2-1]]=1
f[2][2]+=f[0][1]]=1
f[3][1]+=f[3-a[1]][1-1]]=0
f[3][1]+=f[1][0]]=0
f[3][2]+=f[3-a[1]][2-1]]=1
f[3][2]+=f[1][1]]=1
f[3][3]+=f[3-a[1]][3-1]]=1
f[3][3]+=f[1][2]]=1
f[4][1]+=f[4-a[1]][1-1]]=0
f[4][1]+=f[2][0]]=0
f[4][2]+=f[4-a[1]][2-1]]=1
f[4][2]+=f[2][1]]=1
f[4][3]+=f[4-a[1]][3-1]]=1
f[4][3]+=f[2][2]]=1
f[4][4]+=f[4-a[1]][4-1]]=1
f[4][4]+=f[2][3]]=1
3

动态规划很难，对于我来说给出转移方程说不定也写不了。，，