Project Euler Problem 172

Problem 172 - PukiWiki

解法

数字の使用個数でメモ化再帰する

実装(Ruby)

$dp=Array.new(19){Array.new(10){Array.new(10){Array.new(10){Array.new(5,-1)}}}}
def solve(now,three,two,one,zero)
	return 1 if now==18
	return $dp[now][three][two][one][zero] if $dp[now][three][two][one][zero]>=0
	ans=0

	ans+=solve(now+1,three-1,two+1,one,zero)*three if three>0
	ans+=solve(now+1,three,two-1,one+1,zero)*two if two>0
	ans+=solve(now+1,three,two,one-1,zero)*one if one>0
	ans+=solve(now+1,three,two,one,zero+1) if zero<3 && now!=0
	return $dp[now][three][two][one][zero]=ans
end

p solve(0,9,0,0,0)