硬币找零

动态规划

/**
 *    硬币找零， 假如你的硬币面值有1,2,5等，每种面值的都有无数个，求找零100最少要多少个硬币
 *
 */
public class CoinChange {

    public static void main(String[] args) {
        int [] coins = new int[] {1,2,5};
        System.out.println(getMin(coins,11));
    }
    
    public static int getMin(int [] coins  ,  int target) {
        int [] dp = new int [target +1];   //dp 的下标是要组成的钱数
        //若要组成的是0，那么就不需要硬币
        dp[0] = 0;
        //给其余的赋初始值target+1。,在最后返回时候，作判断使用
        for(int i = 1 ; i < dp.length; i++) {
            dp[i] = target+1;
        }
        //假设我取了一个值为5的硬币，那么由于目标值是 11，所以是不是假如我们知道 dp[6]，
        //那么就知道了组成 11 的 dp 值了？所以更新 dp[i] 的方法就是遍历每个硬币，如果遍历到的硬币值小于i值（比如不能用值为5的硬币去更新 dp[3]）时，
        //用 dp[i - coins[j]] + 1 来更新 dp[i]，所以状态转移方程为：
        //dp[i] = min(dp[i], dp[i - coins[j]] + 1);
        for(int i = 1; i < dp.length; i++) {
            for(int j = 0 ; j < coins.length ; j++) {
                if(coins[j] <= i) {
                     dp[i] = Math.min(dp[i], dp[i-coins[j]] +1);
                }
            }
        }
        return   dp[target]==target+1?-1:dp[target];
    }
}