拼凑面额

经典dp
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        System.out.println(dp(N));
    }
    public static long dp(int N) {
        int []arr = {1,5,10,20,50,100};
        //仅用前i种钞票构成j面额
        long [][]dp = new long[7][N + 1];
        dp[0][0] = 1;
        for (int i = 1;i <= 6;i ++) {
            dp[i][0] = 1;
        }
        for (int i = 1;i <= N;i ++) {
            dp[0][N] = 0;
        }

        for (int i = 1;i <= 6;i ++) {
            for (int j = 1;j <= N;j ++) {
                for (int k = 1;j >= k * arr[i - 1];k ++) {
                    dp[i][j] += dp[i - 1][j - k * arr[i - 1]];
                }
                dp[i][j] += dp[i - 1][j];
            }
        }
        return dp[6][N];
    }
}

import java.util.Scanner;
public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] penny = new int[] {1, 5, 10, 20, 50, 100};
        int rows = penny.length, cols = N + 1;
        long[] dp = new long[cols];
        //第一行dp[0][j]
        for (int j = 0; j * penny[0] < cols; j++) {
            dp[j * penny[0]] = 1;
        }
        for (int i = 1; i < rows; i++) {
            dp[0] = 1;
            for (int j = 1; j < cols; j++) {
                dp[j] = dp[j] + ((j - penny[i] >= 0) ? dp[j - penny[i]] : 0);
            }
        }
        System.out.println(dp[cols - 1]);
    }
    
}

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

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

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

大师兄：是的。那我来考考你，假如输入的是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();
    }
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int[] money = {1, 5, 10, 20, 50, 100};
        //dp[i]代表拼凑i元的方法
        long[] dp = new long[num + 1];
        dp[0] = 1;
        for (int i = 0; i < money.length; i++) {
            for (int j = 1; j <= num; j++) {
                if (j >= money[i])
                    dp[j] = dp[j] + dp[j - money[i]];
            }
        }
        System.out.println(dp[num]);
    }
}

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);
        
    }
}