java是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台（即JavaEE, JavaME, JavaSE）的总称。本站提供基于Java框架struts,spring,hibernate等的桌面应用、web交互及移动终端的开发技巧与资料

保持永久学习的心态，将成就一个优秀的你，来 继续搞起java知识。

原题链接：322. Coin Change
【思路-Java】
本题考查动态规划。也许一开始很容易想到用贪心算法，但是贪心算法在某些情况下是不成立的，比如coins = [1, 3, 5, 6]，要amount = 11，用贪心法返回3，实际上最少的是2（3 + 5）。因而改用动态规划，用dp存储硬币数量，dp[i] 表示凑齐钱数 i 需要的最少硬币数，那么凑齐钱数 amount 最少硬币数为：固定钱数为 coins[j] 一枚硬币，另外的钱数为 amount - coins[j] 它的数量为dp[amount - coins[j]]，j 从0遍历到coins.length
- 1：

public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = 0x7fffffff;
            for (int j = 0; j < coins.length; j++)
                if (i >= coins[j] && dp[i - coins[j]] != 0x7fffffff)  //①
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
        }
        return dp[amount] == 0x7fffffff ? -1 : dp[amount];
    }

180 / 180 test
cases passed. Runtime: 24
ms Your runtime beats 78.00% of javasubmissions.
欢迎优化！
【优化】by—— 卡拉比，2016.5.19
非常感谢热心的博友卡拉比提出的优化方案，其代码如下：

public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) dp[i] = 0x7fff_fffe;
        for (int coin : coins)
            for (int i = coin; i <= amount; i++)
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        return dp[amount] == 0x7fff_fffe ? -1 : dp[amount];
    }

180 / 180 test
cases passed. Runtime: 15
ms Your runtime beats 96.29% of javasubmissions.
该方案确实十分巧妙，利用0x7fff_fffe 替代 0x7fff_ffff，同时令硬币 i = coin，这样省去了原先代码①处的判断，从而达到优化效果。
Javaleetcode动态规划

因为水平有限，难免有疏忽或者不准确的地方，希望大家能够直接指出来，我会及时改正。一切为了知识的分享。

后续会有更多的精彩的内容分享给大家。