コインお釣り(java実装)
7202 ワード
コインおつり(ダイナミックプランニング)
import java.util.Arrays;
public class Coin {
static int N=6;//
static int data[] = {1,3,4};//
public static void getNum() {
int sum[] = new int[N+1];
Arrays.fill(sum,Integer.MAX_VALUE-1);
sum[0]=0;
for(int j=1;j<=N;j++) {
for(int i=0;i<data.length;i++) {
if(j>=data[i]){
sum[j] = Math.min(sum[j], sum[j-data[i]]+1);
}
}
}
if(sum[N]==Integer.MAX_VALUE-1) {
System.out.println("-1");
}else {
System.out.println(sum[N]);
}
}
public static void main(String[] args) {
if(N==0) {
System.out.println("0");
}else {
getNum();
}
}
}