拼凑面额

非常经典的01背包问题变种 一维dp即可

#include <iostream>
#include <cstdio>
using namespace std;
//常量区
const int maxn = 1e4 + 5;
int dic[6] = {1, 5, 10, 20, 50, 100}, n;
long long dp[maxn]; 
//函数区
//main函数
int main(){
    scanf("%d", &n);
    for(int i = 0; i <= n; i++) dp[i] = 1;
     for(int i = 1; i < 6; i++)
         for(int j = 1; j <= n; j++)
             if(j >= dic[i]) dp[j] += dp[j - dic[i]];
    printf("%lld\n", dp[n]);
    return 0;
}

#include <iostream>
#include <cstring>

int main() {
	int n = 0;
	std::cin >> n;
	long long dp[n+1];
	memset(dp, 0, sizeof(dp));
	int money[6] = {1, 5, 10, 20, 50, 100};
	dp[0] = 1;
	for (int i = 0; i < 6; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (j >= money[i]) {
				dp[j] += dp[j - money[i]];
			}
		}
	}
	std::cout << dp[n];
}

import java.util.*;

public class Main {      //本人比较菜，想不到用数组做的动态规划，就用了HashMap做的动态规划。   
   static Map<Long,Long> map = new TreeMap<>();   
   public static void main(String[] args) {            
      int[] arr = {100,50,20,10,5,1};    
      Scanner scanner = new Scanner(System.in);     
     int n = scanner.nextInt();     
     System.out.println(digui(arr, 0, n));       
   }           public static long digui(int[] arr,int cur,int money) {     
    if(money == 0) return 1;     
    if(money < 0) return 0;      
    if(arr[cur] == 1) return 1;     
    long key = (long)cur*10000+money;     
    if(map.containsKey(key)) return map.get(key);     
    long sum = 0;     
    for(int i = 0;i <= money/arr[cur];i++) {        
     sum += digui(arr, cur+1, money-arr[cur]*i);   
    }       
   map.put(key, sum);    
    return sum;      }

} 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String h = "";
        try {
            while ((h = bufferedReader.readLine()) != null) {
                int money = Integer.parseInt(h);
                int[] notes = {1, 5, 10, 20, 50, 100};
                long result = getZuHehyc(money, notes);
                System.out.println(result);
              //  bufferedReader.close();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

    }

    public static long getZuHehyc(int money, int[] arr) {
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < money + 1; i++) {
            if (i % arr[0] == 0) {
                dp[0][i] = 1;
            }
        }

        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < money + 1; j++) {
                if (arr[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i][j - arr[i]] + dp[i - 1][j];
                }
            }
        }
        return dp[arr.length - 1][money];
    }
}

	

#include <iostream>
#include <vector>

using namespace std;

int main()
{     int N;     int a[6] = {1,5,10,20,50,100};     cin>>N;      vector<long> dp(N+1,0);     dp[0] = 1;     for(int i=0;i<6;i++)     {         for(int j=1;j<=N;j++)             if(a[i] <= j)                 dp[j] = dp[j] + dp[j-a[i]];     }     cout<<dp[N]<<endl;     return 0;
}

#include <iostream>

using namespace std;

int p[6] = {1, 5, 10, 20, 50, 100};
long long dp[10005];

void init() {
    dp[0] = 1;
    for(int i = 0; i < 6; i++) {
        for(int j = 1; j < 10005; j++) {
            if(j - p[i] >= 0) dp[j] += dp[j - p[i]];
        }
    }
}

int main()
{
    int n;
    cin >> n;
    init();
    cout << dp[n] << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
int main(){     int N;     while(cin>>N){         vector<long> dp(N+1,0);         dp[0]=1;         vector<int> m={1,5,10,20,50,100};         for(int i=0;i<m.size();i++){             for(int j=1;j<N+1;j++){                 if(j>=m[i]){                     dp[j]+=dp[j-m[i]];                 }             }         }         cout<<dp[dp.size()-1]<<endl;     }
}

//成绩8ms,376K
#include<stdio.h>
int main(void)
{
   long ans = 0;
   int n1[4] = {3,4,10,20},n2[4] = {0,0,0,0},in,ju,ju2;
   scanf("%d",&in);in /= 5;
   while(1)
   {
      ju = 0;
      for(int i = 1; i <= n1[0]; i++)
         ju += n1[i] * n2[i];
         if(ju <= in)
            ans += ((in - ju + 1) / 2+ 1) * ((in - ju + 1) + ((in - ju  + 1)) % 2) / 2, n2[1]++, ju2 = 1;
         else
         {
            n2[ju2++] = 0;
            if(ju2 > n1[0])
               break;
            n2[ju2]++;
         }
   }
   printf("%ld\n",ans);
   return 0;
}

	importjava.util.*;



	publicclassMain {



	    /**



	    *有序性：转移方程不能是 f(n) = f(n-1) + f(n-5) + f(n-10) + f(n-20) + f(n-50) + f(n-100), 因1+5和5+1在组合中是一个情况



	    *为了保障有序性，



	    *设价格数组为arrDenomination= {1, 5, 10, 20, 50, 100} 下标为i



	    *我们可以规定转移方程为f（i,j）,j表示总价格，方程的含义为从下标0到i的价格组合总价值j



	    *那么f(i,j) = f(i-1,j) (j<arrDenomination[i])



	    *   f(i,j) = f(i-1,j) + f(i,j-arrDenomination[i]) (j>arrDenomination[i])



	    *   f(i,j) = f(i-1,j) + 1 (j=arrDenomination[i])



	    *递归边界



	    *   f(0,j) = 1;当 j>0;



	    *   f(i,0) = 0;当i>=0,j=0;



	    */



	    publicstaticfinalint[] arrDenomination= {1, 5, 10, 20, 50, 100};



	    publicstaticfinalintintLenOfDenomination = arrDenomination.length;



	    publicstaticvoidmain(String[] args) {



	        Scanner sc = newScanner(System.in);



	        while(sc.hasNextInt()) {



	            intintSum = sc.nextInt();



	            if(intSum < 0) {



	                thrownewIllegalArgumentException();



	            } elseif(intSum == 0) {



	                System.out.println(0);



	            } else{



	                long[] temp = newlong[intSum + 1];



	                for(inti=1; i<temp.length; i++) {



	                    temp[i] = 1;



	                }



	                for(inti=1; i<intLenOfDenomination; i++) {



	                    for(intj=1; j<temp.length; j++) {



	                        if(j > arrDenomination[i]) {



	                            temp[j] += temp[j - arrDenomination[i]];



	                        } elseif(j == arrDenomination[i]) {



	                            temp[j] += 1;



	                        }



	                    }



	                }



	                System.out.println(temp[intSum]);



	            }



	        }



	    }



	}

//1维dp
#include<iostream>
#include<string>
using namespace std;
long long dp[100200];
int main()
{
    int n;
    cin>>n;
    int way[]={1,5,10,20,50,100};
    dp[0]=1;//初始状态
    for(int i=0;i<6;++i)//枚举种类
    {
        for(int j=n;j>=way[i];--j)//dp需要拼凑的面额         
        {
            int k=1;
            while(j>=k*way[i])   //dp选取了多少个way[i]
            {
                dp[j]+=dp[j-k*way[i]];
                ++k;
            }
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

思路：用一个数组记录方法数。dp[i]表示组成i的方法数

初始化：组成为0只有一种方法

递归：dp[j] += dp[j-tables[i]]
意思是，组成dp[j]的方法数是dp[j-tables[i]]的方法数是一致的。

import java.util.Scanner;

public class Main{

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while(sc.hasNext()) {
        int n = sc.nextInt();
        int[] tables = {1,5,10,20,50,100};
        //dp[i]表示组成i的组合个数
        long[] dp = new long[n+1];
        dp[0] = 1;
        for(int i = 0; i < tables.length;i++) {
            for(int j = tables[i]; j < dp.length;j++) {
                dp[j] = dp[j] + dp[j - tables[i]];
            }
        }
        System.out.println(dp[n]);
    }
}

}

应该没有比我这代码更暴力的（虽然没过，时间太长^-^）

#include <stdio.h>
const int one = 1;
const int five = 5;
const int ten = 10;
const int twenty = 20;
const int fifty = 50;
const int hundred = 100;
int main(void) 
{
    int N, sum = 0;
    int i, j, k, l, m, n, count = 0;
    scanf("%d", &N);
    for (i=0; i<=N/one; i++) {
        for (j=0; j<=N/five; j++) {
            for (k=0; k<=N/ten; k++) {
                for (l=0; l<=N/twenty; l++) {
                    for (m=0; m<=N/fifty; m++) {
                        for (n=0; n<=N/hundred; n++) {
                            sum = one*i+five*j
                                +ten*k+twenty*l
                                +fifty*m+hundred*n;
                            if (N == sum) {
                                count ++;
                            }
                        }
                    }
                }
            }
        }
    }
    printf("%d\n", count);
    return 0;
}

import java.util.Scanner;

public class StringUtil {

	//拼凑面额
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int arr[] = {1,5,10,20,50,100};
		while(in.hasNext()){
			int n = in.nextInt();
			long res[] = new long[n+1];
			res[0] = 1L;
			
			for(int i=0; i<arr.length; i++){
				for(int j=1; j<=n; j++){
					if(j >= arr[i]){
						res[j] += res[j-arr[i]];
					}
				}
			}
			
			System.out.println(res[n]);
		}
	}
}

public class Main{
    
       //可以看做完全背包问题：每个数字面额有无限个，求拼成n的组合数
       //状态转移方程：f[i,j] = f[i-1, j-k*a[i]],其中0<=k*a[i]<=j
       //f[i,j]表示前i个面额拼成j的组合数
       //f[i-1, j-k*a[i]]表示前i-1个面额拼成j-k*a[i]的组合数
       //注意：当只有一个数字面额时，f[0,j]= j- k*a[0] == 0 ? 1 : 0
      
        public static long getCombinationNum(int []a, int n){
        long [][] dp = new long[a.length][n+1];

        for (int i=0; i<a.length; ++i) {
            dp[i][0] = 1;
        }
        for (int i=0; i<a.length; ++i){
            for (int j=1; j<=n; ++j){
                int k=0;
                if (i ==0 ){

                    while ( (j-k*a[i]) >=0 ){
                        dp[i][j] = j-k*a[i] == 0  ? 1 : 0;
                        k++;
                    }

                }else {
                    while (j-k*a[i] >=0){
                        dp[i][j] += dp[i-1][j-k*a[i]];
                        k++;
                    }
                }

            }
        }

        return dp[a.length-1][n];
    }
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = {1, 5, 10, 20, 50, 100};
        //int n = 5;
        long count = getCombinationNum(a, n);
        System.out.println(count);
        
    }
}

}

原文链接点这里（点开有惊喜）

大师兄：这个题呀，确实可以用动态规划。我来考考你，还记得动态规划的三要素吗？

小师弟：【最优子结构】、【边界】、【状态转移公式】

大师兄：是的。那我来考考你，假如输入的是1000元，那么这个问题的最优子结构是什么？
为了问题讨论方便，咱们约定一下格式：

• n元钱用最大面值不超过m元的基本面值组合起来的个数，记为A(n,m)，那么1000元用{1，5，10，20，50，100}组合个数记为A(1000,100)，1000元用{1，5，10，20，50}组合个数记为A(1000,50)......1000元用{1}组合个数记为A(1000,1)；
• i元钱的组合中，包含的最大面值为j元（显然j可以取1，5，10，20，50，100）的组合，记为B(i,j)，那么1000元的分配组合中，最大面值为100的记为B(1000,100)，最大面值为1元的记为B(1000,1)。

小师弟：1000元钱的组合可以分为，最大面值为100的，和最大面值小于100的。

大师兄：是的，按照咱们的约定方式，在基本面值为{1，5，10，20，50，100}时，1000元钱的组合记为A(1000,100)，最大面值为100的记为B(1000,100)，而最大面值小于100的组合就相当于用基本面值为{1，5，10，20，50}来组合，所以记为A(1000,50)。

小师弟：所以是不是可以得到，A(1000,100) = B(1000,100) + A(1000,50)。

大师兄：是的，另外B(1000,100)是不是还可以继续化简呢，你想想，1000元钱的组合中最大面值为100的组合，如果拿去了一张100元钱，剩下的组合有什么特点？

小师弟：最大面值为100，说明至少有一张100，现在拿去了一张100，那么就可能一张毛爷爷也没有了，剩下的组合中，基本面值还是{1，5，10，20，50，100}，但是包含的最大面值不一定是100了，因为还剩下900元钱，所以是不是可以认为是用最大面值不超过100元的基本面值来组合900元？也就是A(900,100) 。

大师兄：非常好，所以我们就得到了A(1000,100) =A(900,100) + A(1000,50)。

小师弟：我知道了，这是递推公式，用这个我们就可以用递归来解决问题了。

A(0,100)，A(1000,1)应该就属于边界条件了吧。

大师兄：是的。A(n,m)表示n元钱用最大面值不超过m元的基本面值组合起来的个数。

• 一种情况是A(n,m) (n<m)，就像A(0,100)。组合的最大面值肯定小于m元，如果还存在比m小的面值m-，那么A(n,m)=A(n,m-），如果m已经是最小的面值也就是1时，n肯定为0，这种组合方式的终极问题是A(0,1)。
• 另一种情况是A(n,1) (n>=1)，就像A(1000,1)。n>=1，而m=1时，根据常识，任意正数n元都可以用n张1元钱来组合，这种组合方式个数为1。

小师弟：那这个A(0,1)怎么处理呢？

大师兄：我们来看一下A(0,100)是怎么产生的，它的父节点是A(100,100) = A(0,100) + A(100,50)，含义是100元钱用最大面值不超过100元的基本面值组合起来的个数，可以分为最大面值为100元，和最大面值小于100元两种情况，前一种情况就是B(100,100) = A(0,100)，只有一种组合，就是一张100元，所以 A(0,100) = 1，而后一种情况，100元用最大面值为不超过100元的基本面值来表示，就是A(100,50)。

同理，m >= 1时，根据我们的推理过程B(m,m) = A(0,m)，它对应用一张m元面值表示m元，也就是只有一种组合，所以A(0,m)一定为1。

我们来总结一下得到的所有推论：

【边界】

• A(n,1) = 1 (n>=0)
• A(0,m) = 1 (m=1,5,10,20,50,100)

【状态转移方程】

• A(n,m) = A(n-m,m) + A(n,m-) (n>=m, m-为小于m的面值)
• A(n,m) = A(n,m-) (n<m)

后面就交给你了，把你的代码秀一秀。

小师弟：有了递推公式和边界条件就可以用递归解决了，但是如果N太大，会使递归数深度很大，效率很低，所以这里更适合使用动态规划。动态规划从简单过程往复杂过程计算，并把后面会用到的数据保存下来，避免重复计算。计算备忘录如下：

以A(10,10)为例，A(10,10) = A(0,10) + A(10,5) = 1 + 3 = 4；可见，每一行的计算只需要在上一行的值和这一行前面的值，因此，用一个数组就可以完成。

// @author 小师弟
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();

        int[] m = {1, 5, 10, 20, 50, 100}; // 保存基本面额的数组
        long[] data = new long[num+1]; // 保存计算数据的数组
        for(int i = 0; i <= num; i++) // 边界条件A(n,1) = 1 (n>=0)
            data[i] = 1;
        for(int i = 1; i < 6; i++) // 基本面额从5开始，因为1元情况在数组初始化时已经写入了
            for(int n = 1; n <= num; n++) // n从1开始，保证了边界条件A(0,m)=1 (m=1,5,10,20,50,100)
                if(n >= m[i])
                    data[n] += data[n - m[i]]; // 状态转移方程
        System.out.println(data[num]);
        in.close();
    }
}

/*动态规划
    需要拼凑的面额是n，
    维护dp[i],表示取到i时的组合数目，dp[0]=1，
    面额数组a[6]={1,5,10,20,50,100}，
    dp[j]=dp[j]+dp[j-a[i]],约数条件j>a[i]。
    因为面额数目任意，所以需要分别处理只有面额1时，
    组合钱数为1~n的各自组合数dp[1]~dp[n],
    然后有面额1,5时，组合钱数为1~n的各自组合数dp[1]~dp[n],
    依此内推。。。详情见程序。
*/
#include<iostream>
#include<vector>
using namespace std;

int main()
{
	int n;
	cin >> n;
	int a[6] = {1,5,10,20,50,100};
	vector<long> dp(n+1,0);   //当数字很大时，int表示不够
	dp[0] = 1;
	for (int i = 0; i < 6; i++)
	 {
		for (int j = 1; j <= n; j++)
		  {
	           if (j >= a[i])
		     dp[j] = dp[j] + dp[j-a[i]]; //j值取和不取两种情况组合数目之和
		  }
	 }
	cout << dp[n] << endl;
    return 0;
}