Как составить алгоритм решения задачи на ДП или Рекурсию (Задача на лесенку)?

Question

[Flaker]

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

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

Хотелось бы получить совет о том, какую литературу или статьи почитать, для понимания таких задач.
А так же предложения о том, как решать задачу сабжа.

Мои попытки закончились провалом.
Лучшее к чему я пришел в теории, это подобие рекурсивного алгоритма: habrastorage.org/files/82b/160/5cc/82b1605cc82b414...
(Каждая лесенка уменьшается с конца на 1 кубик, и рассматривается "отрубленная" часть)

Но такой метод привел меня в тупик уже на 13 кубиках:
habrastorage.org/files/cf9/610/866/cf96108666db4ad...

Мой код: pastebin.com/XWE3QZgL

Где-то наткнулся на невероятно красивое решение на Java, переписал его на C++, но для меня это абсолютнейшая магия, возможно кто-то пояснит, что тут происходит, и на какую базу все это опирается: pastebin.com/6ACsC9ta

Answer 1

[Mrrl]

Решить задачу легко - заводите массив A[N,N], в каждой клетке [K,M] которого будет записано число лесенок из K кубиков, нижний слой которых состоит из M кубиков. Число будет ненулевым, когда M <= K <= M*(M+1)/2.
Массив заполняется начиная со строчки K=1 по формуле A[K,M]=sum(A[K-M,r],r=1..M-1). Сумма элементов в строчке K=N будет искомым числом.

В решении, ссылку на которое вы дали, последовательно вычисляется число лестниц из j кубиков, нижний ряд которых не длиннее, чем i кубиков. Чтобы найти это число, надо к уже найденным лестницам, нижний ряд которых не длиннее, чем i-1 кубик (их мы оставляем без изменения), прибавить лестницы из j-i кубиков с нижним рядом не длиннее, чем i-1 кубик (к ним мы добавим ряд из i кубиков). Что и делается во внутреннем цикле.

Comments

[Flaker]

Пытаюсь разобрать и закодить ваше решение, но не понимаю.
Вопросы:
1) Как дойти до этого решения? (Что почитать?)
2) Откуда это условие: M <= K <= M*(M+1)/2
3) В данном случае A[K,M]=sum(A[K-M,r],r=1..M-1) чем будет M?
4) Массив A индексирован с 0 или с 1?

В общем, нужен еще более подробный разбор.

[Flaker]

https://ru.wikipedia.org/wiki/Разбиение_числа
Нашел по теории немного

[Mrrl]

Flaker:
1) Не знаю. Оно ищется "из общих соображений", но какая-то общая база, наверное, нужна.
2) K - число кубиков, M - длина нижнего ряда. Понятно, что K не может быть меньше M (рядов отрицательной длины не бывает). Наибольшее число кубиков при заданной длине нижнего ряда равно M+(M-1)+(M-2)+...+2+1=M*(M+1)/2 - как сумма арифметической прогрессии.
3) ряд A[K,M] для очередного значения K надо заполнять для всех M от 2 до K-1. Потом определить, что A[K,K]=1.
4) В данном случае, с 1. В этой задаче нулевое число кубиков и нулевая длина ступеньки смысла почти не имеют. Впрочем, вы можете задать A[0,0]=1, величину A[K,M] считать как sum(A[K-M,r],r=0..M-1), и тогда A[K,K] будет считаться по общим правилам. Не уверен, нужно ли это.

[Flaker]

Mrrl, большое спасибо.
К сожалению, только сейчас появилось время разобраться до конца. Отметил решением.

[Popou]

Mrrl, я не очень умный, уж простите , но что значит sum(A[K-M,r],r=0..M-1), а конкретно переменная r?