描述
我们知道人民币有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怎么写，求代码。

DP是什么？

n=a+2*b+5*c+10*d+20*e+50*f+100*g用穷举法行不行？

动态规划

。。学习什么算法，用什么。。  而且穷举估计超时

是这样的算法吗？

#include <stdio.h>
/*
**声明金额
*/
#define ONE        1
#define TWO        2
#define FIVE    5
#define TEN        10
#define TWENTY    20
#define FIFTY    50
#define HUNDRED    100


int
main ( void ) 
{
    int money, pre;
    /*
    **金额的数量计数定义为数组，尽量避免直接使用数字
    */
    enum num{ one, two, five, ten, twenty, fifty, hundred } ;
    int deno[hundred+1] = {0} ;

    printf ( "输入金额(1 - 250)：" ) ;
    while ( scanf ( "%d", &money ) && money != 0 ) {
        if ( money < 1 || money > 250 ) {
            printf ( "金额超范围，请重新输入金额(1 - 250)：" ) ;
            continue ;
        }
        pre = 0 ;
        for ( deno[one] = 0;
            deno[one] * ONE <= money;
            deno[one]++ ) {
            for ( deno[two] = 0;
                deno[two] * TWO <= money - deno[one] * ONE;
                deno[two]++ ) {
                for ( deno[five] = 0;
                    deno[five] * FIVE <= money - deno[one] * ONE - deno[two] * TWO;
                    deno[five]++ ) {
                    for ( deno[ten] = 0;
                        deno[ten] * TEN <= money - deno[one] * ONE - deno[two] * TWO - deno[five] * FIVE;
                        deno[ten]++ ) {
                        for ( deno[twenty] = 0;
                        deno[twenty] * TWENTY <= money - deno[one] * ONE - deno[two] * TWO
                            - deno[five] * FIVE - deno[ten] * TEN;
                        deno[twenty]++ ) {
                            for ( deno[fifty] = 0;
                            deno[fifty] * FIFTY <= money - deno[one] * ONE - deno[two] * TWO
                            - deno[five] * FIVE - deno[ten] * TEN - deno[twenty] * TWENTY;
                            deno[fifty]++ ) {
                                for ( deno[hundred] = 0;
                                deno[hundred] * HUNDRED <= money - deno[one] * ONE - deno[two] * TWO
                            - deno[five] * FIVE - deno[ten] * TEN - deno[twenty] * TWENTY - deno[fifty] * FIFTY;
                                deno[hundred]++ ) {
                                    /*
                                    **如果总金额等于输入金额，且张数少于100，则输出
                                    */
                                    if ( deno[one] * ONE + deno[two] * TWO + deno[five] * FIVE + deno[ten] * TEN
                                        + deno[twenty] * TWENTY + deno[fifty] * FIFTY + deno[hundred] * HUNDRED == money 
                                        && deno[one] + deno[two] + deno[five] + deno[ten] + deno[twenty] + deno[fifty] + deno[hundred] <= 100 ) {
                                        
                                        pre += 1 ;
                                        /*
                                        **如不需要打印输出每一种可用方案，可注释这段代码
                                        */
                                        printf ( "方案%2d> ", pre ) ;
                                        if ( deno[one] != 0 )
                                            printf ( "￥001:% 2d张 ", deno[one] ) ;
                                        if ( deno[two] != 0 )
                                            printf ( "￥002:% 2d张 ", deno[two] ) ;
                                        if ( deno[five] != 0 )
                                            printf ( "￥005:% 2d张 ", deno[five] ) ;
                                        if ( deno[ten] != 0 )
                                            printf ( "￥010:% 2d张 ", deno[ten] ) ;
                                        if ( deno[twenty] != 0 )
                                            printf ( "￥020:% 2d张 ", deno[twenty] ) ;
                                        if ( deno[fifty] != 0 )
                                            printf ( "￥050:% 2d张 ", deno[fifty] ) ;
                                        if ( deno[hundred] != 0 )
                                            printf ( "￥100:% 2d张", deno[hundred] ) ;
                                        printf ( "\n" ) ;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        printf ( "**********总共%d分配方案**********\n", pre ) ;
    }    
    return 0 ;
}

把我的跟帖删了？

原来是另开帖子了

动态规划不会，穷举法的有一个
#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 21:02 编辑 ]

6楼和9楼代码编译后运行的结果不同，哪个对呢？请测试101及以后的数字。
一个7层的嵌套循环，一个循环加递归，都是天书啊，我是看晕了。