Problem 31

问题描述：

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1£1 + 150p + 220p + 15p + 12p + 31p

How many different ways can £2 be made using any number of coins?

 

 

解决问题：

 

 

可以使用若干个for循环计算

 

  for(int i=0;i<=2;i++){ //100
  for(int j=0;j<=4;j++){ //50
  for(int k=0;k<=10;k++){ //20
  for(int l=0;l<=20;l++){ //10
  for(int m=0;m<=40;m++){ //5
  for(int n=0;n<=100;n++){ //2
  int t = 200 - i*100 - j*50 - k*20 - l*10 - m*5 - n*2;
  if(t>=0 ){
  ++index;
  }
  }
  }
  }
  }
  }
  }

 

最好使用动态规划递归来计算，然后再使用非递归形式。

 

 

  

	private static int[] coinValue = { 200, 100, 50, 20, 10, 5, 2 };
	public static int count = 0;
	
	public static void total(int level, int remain){
		
		if(remain>=0){
			count++;
		}else{
			return ;
		}
		int i=level ;
		for(; i<7; i++){
			total(i, remain - coinValue[i]);
		}
	}