poj3181 Dollar Dayz (DP+大数)

        1 @ US$3 + 1 @ US$2 
 1 @ US$3 + 2 @ US$1 
 1 @ US$2 + 3 @ US$1 
 2 @ US$2 + 1 @ US$1 
 5 @ US$1

5 3

5

其中dp数组存贮组成当前数的个数

import java.math.*;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sca =new Scanner(System.in);
		int k,n;
		while(sca.hasNext())
		{
			n=sca.nextInt();
			k=sca.nextInt();
			BigInteger dp []=new BigInteger[1005];
			for(int i=0;i<1005;i++)
				dp[i]=BigInteger.ZERO;
			dp[0]=BigInteger.ONE;
			for(int i=1;i<=k;i++){
				for(int j=0;j<=n;j++){
					if(j>=i&&dp[j-i]!=BigInteger.ZERO){
						dp[j]=dp[j].add(dp[j-i]);
					}
				}
			}
			System.out.println(dp[n]);
		}
		
	}
}

poj3181 Dollar Dayz (DP+大数)

原文：http://blog.csdn.net/su20145104009/article/details/51539320