$dp[n][k] $ رو تعریف میکنیم تعداد راه های نوشتن تعدادی عدد طبیعی که جمعشون برابر با $n$ بشه و هیچ یک از این اعداد از $k$ بزرگتر نیستن.

حالا اگه تو این اعداد $k$ نیومده باشه که جواب میشه همون $dp[n][k-1]$ اگه $k$ اومده باشه میشه $dp[n-k][k]$

پس در نظر میگیریم: $dp[0][1] = 1$ و $dp[i][j] = dp[i][j-1] + dp[i-j][j]$

جواب هم برابر با $dp[100][99]$ هستش

بله یک بعدیش با توجه به اعداد 5 ضلعی در نظریه اعداد حل میشه. http://en.wikipedia.org/wiki/Pentagonal_number_theorem یک مقدار ی سخت تره ولی واقعا قشنگه. یه خلاصه ای ازش اینه که میگه $p[n]$ رو تعداد راه های افراز عدد n به اعداد کوچکتر و مساوی n بنامیم (دقت کنید که تعدادی که به دست میاد دقیقا یکی از تعدادی که شما در نظر دارید بیشتره، مثلا برای 5 یک علاوه بر 1 + 4 و 3 + 2 و ... یک حالت رو هم خود عدد 5 در نظر میگیره و در کل 7 حالت به دست میاره در ضمن این اعداد به ازای اعداد منفی 0 و به ازای 0، 1 هستند) و اگر اعداد پنج ضلعی با $g[i]$ نشون بدیم (اعداد پنج ضلعی مثل اعداد مثلثی و مربعی هستند، اعداد مثلثی : $n * (n + 1) / 2$ اعداد مربعی : $n ^ 2$ اعداد 5 ضلعی : $n * (3n - 1) / 2 $) این رابطه وجود خواهد داشت :

$$p[n] = p[n - g[1] ]+p[n - g[-1]] - p[n - g[2]] - p[n - g[-2]] + p[n - g[3]] + p[n - g[-3]] - ...$$

دقت کنید با اینکه دنباله تا ابد ادامه داره ولی از یه جایی به بعد که $n < g[i]$ میشه $p[n - g[i]]$ برابر 0 میشه و برای یک n طبیعی به سادگی در میاد. به علاوه راهی که در بالا ارائه شد از $O(n ^ 3)$ هستش ولی چیزی که الان ارائه شد از $O(n ^ 2)$( در عمل از این مقدار کمتره) کدش تقریبا یه همچین چیزی میشه :

من خودم مجبور شدم این کد رو برای سوال 78 پروجکت اویلر بزنم چون گرچه سوالات قبلی با همین راه گفته شده حل میشد ولی سوال 78 به همچین اردری نیاز داره.