• \(K\) を、\(N\) 個の \(1, \frac{1}{2}, \frac{1}{4}, \dots\) に分解する方法は何通り？

というのが今回の問題で求めたいものです。

\(1\) を \(1\) 個以上使うかどうかで場合分けをします。

使う場合

求めたいものは

• \(K - 1\) を、\(N - 1\) 個の \(1, \frac{1}{2}, \frac{1}{4}, \dots\) に分解する方法は何通り？

と等しくなります。

使わない場合

求めたいものは

• \(K\) を、\(N\) 個の \(\frac{1}{2}, \frac{1}{4}, \dots\) に分解する方法は何通り？

と等しくなります。ここで、全ての値を \(2\) 倍することで、これは

• \(2K\) を、\(N\) 個の \(1, \frac{1}{2}, \frac{1}{4}, \dots\) に分解する方法は何通り？

と等しいことがわかります。

以上より、dp[N][K]をこの問題の答えとして、dp[N][K] = dp[N-1][K-1] + dp[N][2K] という漸化式が得られます。

dp[N][K]の定義より \(N < K\) ならば dp[N][K] = 0 であることに注意すると、\(O(N^2)\) でこの問題を解くことが出来ます。