Просмотр кода страницы ACMP 646

== Ссылка на задачу ==
* [http://acmp.ru/?main=task&id_task=646 ACMP #646 &mdash; Сладкие забавы]

== Комментарии ==

Вид подзадачи: d[i][j] &mdash; количество способов набрать i конфет, используя коробки 0..j. 

Рекуррентная формула: d[i][j] = d[i][j - 1] + d[i - w[j]][j - 1].

База рекурсии: d[0][0] = 1.

Вид ответа: max(0, 2<sup>n</sup> - 2 &times; &sum;d[i][n]), где i &isin; 0..(k - 1). Сложность O(N<sup>2</sup>).

[[Category: Сборник задач: ACMP]]
[[Category: Задачи: Динамическое программирование &mdash; параметр, префикс]]