高频面试题总结 —— 动规之拼凑面额

高频面试题总结 —— 动规之拼凑面额

原题地址

题目描述：

给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0-10000的非负整数）的不同组合的个数。

样例：
输入
5
输出
2

思路：

• 很明显，这是背包问题的变种，需要用到动态规划来解
• 用dp[i][j]表示当有前i种面额时，组成j元的不同组合的个数

状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i]]

tips：
每一次都是基于前面一次的结果，即无后效性，为了降低空间复杂度，我们可以做如下改进：

dp[j] = dp[j] + dp[j-coins[i]]

代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int sum = scan.nextInt();
        //为int时只能 ac 80%
        long[] dp = new long[sum+1];
        dp[0] = 1L;
        int[] coins = new int[]{1, 5, 10, 20, 50, 100};
        for (int i = 0; i < coins.length; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j >= coins[i])
                    dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        System.out.println(dp[sum]);
    }
}