[数据结构与算法]货币组合成aim的种类数

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的种类数。

输入描述:

输入包括两行，第一行两个整数n（0<=n<=1000）代表数组长度和aim（0<=aim<=5000），第二行n个不重复的正整数，代表arr。

输出描述:

输出一个整数

示例1

输入

3 10
5 2 3

输出

4

示例2

输入

4 350
5 2 3 1

输出

249582

暴力递归：

import java.util.Scanner;

public class Coins {
	public static int coinWays(int[] arr,int aim) {
		if(arr==null||aim<0)return 0;
		return process(arr,0,aim);
	}
	public static int process(int[] arr,int index,int left) {//index:只能从index及其往后的钱币里面选择， left：剩下的钱
		int N=arr.length;
		if(index>=N) {
			return left==0?1:0;
		}
		int ans=0;
		for(int num=0;num*arr[index]<=left;++num) {
			ans+=process(arr,index+1,left-num*arr[index]);
		}
		return ans;
	}
	 
	public static void main(String[] args) {
		int n,aim;
		Scanner scan=new Scanner(System.in);
		n=scan.nextInt();
		aim=scan.nextInt();
		int[] arr=new int[n];
		for(int i=0;i<n;++i) {
			arr[i]=scan.nextInt();
		}
		int ans1,ans2;
		ans1=coinWays(arr,aim);
		System.out.println(ans1);
	}
}

动态规划：

共有index，left两个可变参数，建立一张二维表。 index : 0 ~ N ; left : 0 ~ aim 。

初始化：

if(index>=N) {
			return left==0?1:0;
		}

很明显，第N行中, dp [N] [0] 位置填1,其余都填0。

状态转移方程：

下面的二维表中：
红色格子dp[0][aim]为所求,由暴力递归可知，绿色格子的值关联其下面一行的蓝色位置的格子，而这些蓝色格子又被橙色格子所关联，所以最后，绿色格子与橙色格子及绿色格子正下方的蓝色格子相关联。（其中蓝色格子之间的间距是arr[i],i为绿色格子所在行号）。

import java.util.Scanner;

public class Coins {
	
	public static int DP(int[] arr,int aim) {
		int N=arr.length;
		int[][] dp=new int[N+1][aim+1];
		dp[N][0]=1;
		for(int i=N-1;i>=0;--i) {
			for(int j=0;j<=aim;++j) {
//				dp[i][j]=dp[i+1][j]+
//						dp[i][j-arr[i]];
				dp[i][j]=getValue(arr,dp,aim,i+1,j)+getValue(arr,dp,aim,i,j-arr[i]);
			}
		}
		return dp[0][aim];
	}
	public static int getValue(int[] arr,int[][]dp, int aim,int i,int j) {
		if(i<0||i>arr.length||j<0||j>aim)return 0;
		return dp[i][j];
	}
	public static void main(String[] args) {
		int n,aim;
		Scanner scan=new Scanner(System.in);
		n=scan.nextInt();
		aim=scan.nextInt();
		int[] arr=new int[n];
		for(int i=0;i<n;++i) {
			arr[i]=scan.nextInt();
		}
		int ans1,ans2;
		ans2=DP(arr,aim);
		System.out.println(ans2);
	}
}