有一个数组changes，changes中所有的值都为正数且不重复。 每个值代表一种面值的货币，每种面值的货币可以使用任意张， 对于一个给定值x，请设计一个高效算法，计算组成这个值的方案数。 给定一个int数组changes，代表所以零钱，同时给定它的大小n， 另外给定一个正整数x，请返回组成x的方案数，保证n小于等于100且x小于等于10000。 测试样例： 4 15 5 10 25 1 返回：6 测试样例： 4 0 5 10 5 1 返回：1
public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int x=sc.nextInt(); int changes[]=new int[n]; for(int i=0;i<n;i++){ changes[i]=sc.nextInt(); } sc.close(); //--------------------初始化----------------------- int[][]dp=new int[n][x+1];//用前i种货币组成j的方案数 for(int i=0;i<n;i++){//组成0元的方案数 dp[i][0]=1; } for(int j=1;j<=x;j++){//用第一种货币组成j的方案就是1种 if(j%changes[0]==0){ dp[0][j]=1; } } //----------------------规划----------------------- for(int i=1;i<n;i++){//changes[i]看做物品重量 for(int j=1;j<=x;j++){//看做背包的容量 dp[i][j]=dp[i-1][j]; if(j-changes[i]>=0){//若背包能装下changes[i] dp[i][j]+=dp[i][j-changes[i]]; } } } System.out.println(dp[n-1][x]); } }