Introduction
给你一个非负整数n，再给你一个整数数组nums表示不同面值的硬币。
请你计算并返回可以凑成总金额n的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
n和nums都在int整数范围内
Input
第一行输入整数n和m。n表示总金额数(1<=n<=10000)，m表示数组的元素个数。(1<=m<=10)
第二行输入互不相同的m个整数表示不同面值的硬币，每个数字用空格隔开。硬币面值不大于10000
Output
输出可以凑成总金额的硬币组合数
Sample
input
5 3 1 2 5
output
4
Solution
import java.util.Scanner; public class Main { static int n,m,ans=0; static int[] arr; public static void main(String[] args) { Scanner s=new Scanner(System.in); n=s.nextInt(); m=s.nextInt(); arr=new int[m]; for(int i=0;i<m;i++){ arr[i]=s.nextInt(); } int[] dp = new int[n + 1]; dp[0] = 1; for (int coin : arr) { for (int i = coin; i <= n; i++) { dp[i] += dp[i - coin]; } } System.out.println( dp[n]); } }
Experience
刚开始想的是完全背包问题，感觉有些出入。通过类似的动态规划，然后就能求解出。
它的一维优化，和完全背包问题的一维优化类似。
