ダイナミックプランニング法コインのお釣りを解く(Java)

アルゴリズムの説明:
動的計画アルゴリズムは、通常、ある最適な性質を有する問題を解くために使用される.このような問題では,実行可能な解がたくさんあるかもしれない.各解は1つの値に対応し,最適値を持つ解を見つけたい.基本思想も,解くべき問題をいくつかのサブ問題に分解し,まずサブ問題を解き,サブ問題の結果を保存し,これらのサブ問題の解から元の問題の解を得る.動的計画は実質的に空間で時間を変える技術であり、実現過程で発生過程の様々な状態を記憶しなければならないため、その空間複雑度は他のアルゴリズムより大きい.
問題の説明:
V 1、V 2、V 3...単位の硬貨の山に現存していますが、少なくともT単位の小銭を見つけるには何個の硬貨が必要ですか?
問題解決の考え方:
1,Tに最も近い硬貨Vを見つけ出す
2,f(T)問題の解をf(T-V)+1問題の解に変換して再帰する
コード実装:
CoinChangeクラスは、コインのお釣りを処理するためのビジネスです.

public class CoinChange {
	/**
	 *         
	 * @param coinValue        
	 * @param totalValue        
	 * @return
	 */
	public int coinNum(int[] coinValue,int totalValue){
		List<Integer> coins=new ArrayList<Integer>();
		coins.add(0);
		for(int i=1;i<=totalValue;i++){
			int coin=nearestCoin(i,coinValue);
			int coinNum=coins.get(i-coin)+1;
			coins.add(coinNum);
		}
		return coins.get(totalValue);
	}
	/**
	 *               
	 */
	private int nearestCoin(int value,int[] coinValues){
		int res=0;
		int nearest=Integer.MAX_VALUE;
		for(int coinValue:coinValues){
			if(coinValue<=value){
				int distance=value-coinValue;
				if(distance<nearest){
					nearest=distance;
					res=coinValue;
				}
			}
		}
		return res;
	}
}

Mainクラスはテストに使用されます.

public class Main {
	public static void main(String[] args) {
		CoinChange coinChange=new CoinChange();
		int res=coinChange.coinNum(new int[]{1,2,3,5,11},81);
		System.out.println(res);
	}
}

印刷出力:9