322.Coin Change|Java最短コード実装

原題リンク:
322. Coin Change
【考え方】
本題は動的計画を考査する.最初は欲張りアルゴリズムを使うことを考えやすいかもしれませんが、欲張りアルゴリズムは場合によっては成立しません.例えばcoins=[1,3,5,6]、amount=11で、欲張り法で3を返します.実際に最も少ないのは2(3+5)である.そこで動的計画に変更し、硬貨の数をdp[i]で記憶し、dp[i]はお金の数iを揃えるのに必要な最小硬貨数を表す.では、お金の数amountの最小硬貨数は、固定硬貨数がcoins[j]1枚の硬貨であり、また、お金の数がamount-coins[j]であり、その数はdp[amount-cois[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.
最適化を歓迎します.