LeetCode322. 凑零钱，使用三种方式解决

动态规划是最优的，它自底向上来解决问题

<?php 

//leetcode 322. 零钱兑换
//func2([1,2,5], 38) 比 func([1,2,5], 38) 快多了，但是func2运行 func2([186,419,83,408], 6249)会很慢，所以继续优化，使用动态规划

//方法1. 暴力无脑递归求解
function func($coins, $amount){
    if($coins && !$amount){
        return 0;
    }
    if(count($coins) <= 0 || $amount < 0){
        return INF;//这里不能用-1，不然的话有问题，因为-1肯定是最小的。求最小值，所以初始化为比较大的数
    }
    if(count($coins) >= 1 && in_array($amount, $coins)){
        return 1;
    }
    
    //echo $amount."--".implode(',', $coins)."\n";
    
    $result = INF;
    for($i = 0; $i < count($coins); $i++){
        $a = 1 + func($coins, $amount - $coins[$i]);    //选 注意需要加1
        $result = min($a, $result);
    }
    
    return $result;
}

//方法2. 带备忘录的递归
$memory = [];
function func2($coins, $amount){
    global $memory;
    if(isset($memory[$amount])){
        //echo $amount."\n";
        return $memory[$amount];
    }
    if($coins && !$amount){
        return 0;
    }
    if(count($coins) <= 0 || $amount < 0){
        return INF;//这里不能用-1，不然的话有问题，因为-1肯定是最小的。求最小值，所以初始化为比较大的数
    }
    if(count($coins) >= 1 && in_array($amount, $coins)){
        return 1;
    }
    
    
    
    $result = INF;
    for($i = 0; $i < count($coins); $i++){
        $a = 1 + func2($coins, $amount - $coins[$i]);   //选 注意需要加1
        $result = min($a, $result);
    }
    
    if($result != INF){
        $memory[$amount] = $result;
    }
    
    return $result;
}


//方法3. 动态规划[用了1，3，5面值的钱]
//f(i) = min{ 1 + f(i - 1), 1 + f(i - 3), 1 + f(i - 5) }


function func3($coins, $amount){
    for($i = 1; $i <= $amount; $i++){
        $dp[$i] = INF;//初始化为最大，方便后面用最小值取值来使用
    }
    $dp[0] = 0;
    
    for($i = 1; $i<= $amount; $i++){
        /*
        这段foreach 其实是 f(i) = min{ 1 + f(i - 1), 1 + f(i - 3), 1 + f(i - 5) } 的简化
        */
        foreach($coins as $coin){
            //当前凑n元，但是硬币有coin面值 
            if($coin > $i){
                continue;
            }
            $dp[$i] = min($dp[$i], 1 + $dp[$i - $coin]);
        }

    }
    return $dp[$amount];
}

$result = func2([186, 419, 83, 408], 6249);
//$result = func3([1, 3, 5], 28);
var_dump($result);