Coin Change Problem

coin-change-problem

function count_change ($money, $coins) {
    sort($coins, SORT_NUMERIC);
    $money = (int) $money;
    $ways = array(); // ['denom' => [ 'value' => 'numWays' ]]
    
    foreach ($coins as $_c => $_denom) {
        for ($_m = 0; $_m <= $money; $_m++) {
            if ($_m === 0) {
                $ways[$_c][$_m] = 1;
                continue;
            }
            
            if ($_m < $_denom) {
                $numWays = isset($ways[$_c-1])
                    ? $ways[$_c-1][$_m]
                    : 0;
                $ways[$_c][$_m] = $numWays;
                continue;
            }
            
            $prevVal = $ways[$_c][$_m-$_denom];
            $prevDenom = $ways[$_c-1][$_m];
            $numWays = $prevVal + $prevDenom;
            
            $ways[$_c][$_m] = $numWays;
        }
    }
    
    return $ways[$_c][$money];
}