CodeIQ：切手の選び方は何通り？

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「切手の選び方は何通り？」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

現在、普通切手は以下の19種類の金額が発売されています。
[1, 2, 3, 5, 10, 20, 30, 50, 62, 82, 92, 100, 120, 140, 205, 280, 310, 500, 1000]
※それぞれ、単位は円
（参考：日本郵便）

これらの切手をそれぞれ1枚ずつ持っているとき、ある金額を作る切手の選び方が何通りあるかを求めます。
※同じ金額でデザインが異なる切手はありますが、一つの金額に対して1枚ずつ持っているものとします。

例えば、70円を貼りたい場合、以下の5通りがあります。
(1) 62 + 5 + 3
(2) 62 + 5 + 2 + 1
(3) 50 + 20
(4) 50 + 10 + 5 + 3 + 2
(5) 30 + 20 + 10 + 5 + 3 + 2

標準入力から貼りたい金額が与えられたとき、その切手の選び方が何通りあるかを求め、標準出力に出力してください。
なお、入力される金額は3012円以下の正の整数とします。

【入出力サンプル】
標準入力

70

標準出力

5

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

STAMPS = [1, 2, 3, 5, 10, 20, 30, 50, 62, 82, 92, 100, 120, 140, 205, 280, 310, 500, 1000].reverse

$Memo = {}

def solve(n, mn)
	return $Memo[[n, mn]] if $Memo[[n, mn]] != nil
	if n == 0 then return 1
	elsif n < 0 then return 0
	end

	ret = 0
	for i in mn...STAMPS.size
		next if n < STAMPS[i]
		ret += solve(n-STAMPS[i], i+1)
	end

	$Memo[[n,mn]] = ret
	return ret
end

# main
while line = gets
	line.strip!
	next if line.empty?

	p solve(line.to_i, 0)
end

解説

よくあるタイプの素直な問題です。

考え方

典型的なメモ化再起の問題です。

メモ化のことを考えない場合、次のようになります。
切手から1種類を選びます。
入力値nからその金額を引いて、再帰呼び出しします。
nが0になっていたらOKで1を返します。マイナスになっていたらNGなので0を返します。プラスの値なら前回選んだ金額よりも小さい金額の切手を選んで同じことを繰り返します。
（私は金額の大きいものから優先しましたが、金額の小さい方から選んでも同じです。大きい金額から始めた方が途中で処理を落ち切れることが多いので、nが全ての切手を使う場合以外の時には速いですが、最悪のパターンでは同じです）

あとはメモ化すれば大丈夫で、メモのキーはその時のnと最大額の切手（実際のコードは配列のインデックス番号）、値はパターン数になります。

main

入力値を数値にしてsolve()に渡し、結果を印字します。
STAMPSは切手の金額を配列にしたもの（降順なのでreverseしています）、$Memoはメモです。

solve(n)

問題を解きます。
引数nは残りの金額、mnはSTAMPSから選ぶ切手の最小のインデックス番号です。

$Memoに答えがあればその金額と使用可能な切手の種類でのパターン数は計算済みなのでそれを返します。
n=0なら1、n<0なら0を返します。

それ以外の場合は使用可能な切手の中から1つを選んでsolve()を再帰呼び出しします。
retはパターン数なのでsolve()の戻り値を加算します。

最終的に戻ってきたsolve()のretが答えになります。

雑感

典型的なメモ化再起の問題でした。