题目：

给定一串零钱面额和需要找的零钱数。求需要找的零钱数量的最小值。

举例：
零钱面额：1，2，5，21，25
零钱数：63
结果：3（21*3）

---

思路：

此题可以使用动态规划的思想求解。首先需要明确动态规划的数组的意义，dp[i]代表着当零钱数为i的时候需要找的最小零钱数是多少。其次是状态方程：

dp[i] = Math.min(dp[i], dp[j] + dp[i - j])

Note：j是小于i的任意一个数，该方程的意义是找出当前已知的零钱最少数和未知的零钱最少数谁最小。

首先需要创建一个dp数组初始值设为零，存在于零钱数组中的数设为1。之后动态规划进行查找，查找出给定的零钱数i之前所有零钱的最小值直到最后的i。

Note：动态规划的过程中需要判断dp[i]是否为零，如果为零，则将dp[j] + dp[i - j]赋给dp[i]。

---

代码：

/**
     * Find the minimal number of coins.
     * @param coins
     * @param amount
     * @return
     */
    public int solution(int [] coins, int amount){
        if(coins == null || coins.length == 0 || amount == 0)
            return 0;
        int length = amount > coins[coins.length - 1] ? amount : coins[coins.length - 1];
        int [] dp = new int [length + 1];
        for(int i = 0;i<coins.length;i++){
            dp[coins[i]] = 1;
        }
        for(int i=1;i<=amount;i++){
            for(int j=0;j<i;j++){
                if(dp[i] == 0){
                    dp[i] = dp[j] + dp[i-j];
                }else{
                    dp[i] = Math.min(dp[j] + dp[i-j], dp[i]);
                }
            }
        }
        return dp[amount];
    }