問題
提出コード
解法
正四面体数を記録して、重複可能ナップサック問題を解いていきます。
dp[i][j] = i番目までを使用して、数がjになるような組み合わせの中の最小個数
= i番目の正四面体数
とすると、
dp[i][j] = min(dp[i-1][j],dp[i][j-]+1)
となります。
そして、実はiの添え字の部分は削除しても問題ないので、これによりメモリオーバーを解決できます。
奇数のみのパターンも、同様にして処理できるので、このDPを利用して前計算をし、最後にクエリにこたえていけば答えが求まります。
