Представить число в виде суммы слагаемых по возрастанию

dp[сколько кубиков использовали,какой длины ставим ступень]. Тогда dp[i,j]=dp[i-j,1]+dp[i-j,2]+...+dp[i-j,j-1].

О, три года не мог решить эту задачу, пока внезапно не начал понимать динамику.

dp[all][last] — сколько способов сделать лестницу, если всего использовано all кубиков и в последнем столбце их last штук.

Пробуем в следующий столбец поставить next кубиков (ясно, что должно соблюдаться next > last и all + next <= n).
Тогда dp[all + next][next] += dp[all][last].

Ответ — сумма dp[n][i] по всем i.

Огромное всем спасибо! я её сдал!

Комментарий удален администрацией по причине несоблюдения правил сайта.