1. 概述

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.

可以假设：

  1. 每种硬币均有无数个

  2. 总金额不会超过10000

  3. 硬币的种类数不会超过500, 每种硬币的面额不会超过100

示例：

  1. 输入：
  2. [1, 2, 5]
  3. 11
  4. 输出： 3
  5. 解释： 11 = 5 + 5 + 1

2. 解题

<?php
class Solution
{
    /**
     * @param $coins
     * @param $amount
     * @return int : the fewest number of coins that you need to make up
     */
    public function coinChange($coins, $amount)
    {
        $f[0] = 0;
        for ($i = 1; $i <= $amount; $i++) {
            foreach ($coins as $coin) {
                $preI = $i - $coin;
                if ($preI < 0) continue;

                $f[$i] = $f[$preI] + 1;
                $f[$i] = min($f[$i], $f[$preI] + 1);
            }
            $f[$i] = $f[$i] ?? PHP_INT_MIN;
        }
        return $f[$amount] > 0 ? $f[$amount] : -1;
    }
}

$coins = [1, 2, 5];
$amount = 11;
$cls = new Solution();
$r = $cls->coinChange($coins, $amount);
echo $r;