Project Euler Problem 172
解法
数字の使用個数でメモ化再帰する
実装(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)