Список разборов

Интересная задачка на динамику... Создаем матрицу (N+1)x(N+1), в которой элемент A[i][j] - это количество способов раазложить число i на сумму различных чисел с максимальным слагаемым меньше либо равным j. Для j > i, естественно, A[i][j] = A[i][i], так ка...

На первый взглад задача заставляет нас задуматься над ее решением, но прочитав внимательно, понимаешь, что это задача на динамику, причем несложную. На самом деле нас просят перевести число в бинарный вариант, а затем взять самый старший бит и...

Аза, твое решение конечно правильное, но не оптимальное.

Все можно сделать в одно-мерном массиве. a[1]=1;
i 1..n
j n..i
a[j]=a[j]+a[j-i]

в конце пишем a[n]