HackerRank - The Coin Change Problem Solutions in PHP

はじめに

こんにちは！！！
ミャンマー人エンジニアのピェッピョーアウンです。

今回はHackerRankのThe Coin Change Problemを再帰的関数を利用して実装してみました！
皆さんにとって、参考になると嬉しいです。

The Coin Change Problem

通貨両替問題とはさまざまな通貨を利用して、与えられた金額に対して、両替できる方法の数を計算する問題になります。
皆さんがわかるようにいくつか例をピックアップしてきました。
詳細はThe Coin Change Problemにてご確認ください。

例１：

入力: 両替する合計金額 n = 4, 通過 coins[] = {1,2,3},
出力: 4
説明: 両替できる方法: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}

例２：
入力: 両替する合計金額 n = 10, 通過 coins[] = {2, 5, 3, 6}
出力: 5
説明: 両替できる方法:
{2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5}, {5,5}

再帰的アプローチ

この問題はDynamic Programmingの中でも2-D配列を使った考え方とメモリのスペースを最適化した1-D配列 といったたくさんの解決方法がありますが今回は再起的なアプローチで解決していきます。

疑似コードとして

1. コインには、① 含めるか、②除外するかの２つの選択肢があります。
2. 左側：含めるときは、count(coins, n, sum – coins[n-1])
3. 右側：除外するときは、count(coins, n-1, sum)
4. 最後の数は両方を足算した結果：count(coins, n, sum – coins[n-1] ) + count(coins, n-1, sum )

という感じです。

上記の疑似コードをPHPで書いてみました。

function coun($coins, $n, $sum) {
    if ($sum == 0)
        return 1;
    
    if ($sum < 0)
        return 0;

    if ($n <= 0)
        return 0;

    return coun($coins, $n - 1,$sum ) +
           coun($coins, $n, $sum - $coins[$n - 1] );

}

$fptr = fopen(getenv("OUTPUT_PATH"), "w");
$first_multiple_input = explode(' ', rtrim(fgets(STDIN)));
$n = intval($first_multiple_input[0]);
$m = intval($first_multiple_input[1]);
$c_temp = rtrim(fgets(STDIN));
$c = array_map('intval', preg_split('/ /', $c_temp, -1, PREG_SPLIT_NO_EMPTY));
$ways = coun($c, count($c), $n);
fwrite($fptr, $ways . "\n");
fclose($fptr);

再帰的アプローチの感想

再帰的アプローチはあくまでたくさんの方法の中の一つの解決方法です。個人的な意見として重複したサブ問題をたくさん計算しなければならないので効率的にはベストとは言えないです。考え方がシンプルで分かりさすさがあるのが再起的なアプローチのメリットになります。
この記事を読んで何かお役立ちできると嬉しいです！
最後まで読んでいただき、ありがとうございました。