#13/20 DP: Coin Change [Cracking the Coding Interview Challenges]

#13 DP: Coin Change

www.hackerrank.com

タイトルどおり、Dynamic Programming で解く問題。

以下のような入力が与えられる。

4 3
1 2 3

4 3 # {コインの組み合わせで達成したい値} {コインの種類数}
1 2 3 # コインの種類。この場合、価値が1, 2, 3の3種類のコインが存在するということになる

各コインが無限に利用可能である場合、達成したい値(上記の場合4)を達成する組み合わせが何通り存在するかを計算する。

上記の入力の場合

1,1,1,1
1,1,2
2,2
1,3

の4種類の組み合わせがあるため、4を出力すれば良い。

solution

以下 ruby での解。

#!/bin/ruby

def solution(coins, target)
    lenCoins = coins.size
    table = Array.new(lenCoins + 1).map{Array.new(target + 1,0)}
    for i in 0..lenCoins
        table[i][0] = 1
    end

    for i in 1..lenCoins
        for j in 1..target
            table[i][j] = coins[i - 1] <= j ?
                table[i - 1][j] + table[i][j - coins[i -1]]
                : table[i - 1][j]
        end
    end
    return table[lenCoins][target];
end

input = $stdin.read.split("\n")
n, m = input[0].split(" ").map(&:to_i)
coins = input[1].split(" ").map(&:to_i)
puts solution(coins, n)

動的計画法に倣って、まず小さい問題に分割、ボトムアップで順次に解を得ていくというアプローチで解いた。ソースコード内table配列が全ての部分結果を保持する。

追加するコインの値がtarget値より大きい場合

table[i - 1][j] を参照する。合計値をオーバーするためこの場合、既に算出している自身より1ワイズ小さいコインの結果を参照する。

追加するコインの値がtarget値以下の場合

table[i - 1][j] + table[i][j - coins[i -1]] を参照する。自身のコインを追加できる場合、目標値は(target - コインの値)と考えることができるので既に算出済みの table[追加するコインindex][(target - 追加するコインの値)] を加算している。

github.com

Dynamic Programming(動的計画法)とは

動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

動的計画法 - Wikipedia

感想

動的計画法、すらすらと書けないなあ。解いてみるとすごくシンプルなんだけど。