Як скласти алгоритм розв'язання задачі на дп або рекурсію (завдання на драбинку)
- програмування
- Математика
- C ++
- алгоритми
- олімпіадне програмування
Читав, що такі завдання вирішуються так званим "Динамічним Програмуванням", але на жаль, хоча і розумію суть цього методу, навички рішень оллімпіадних завдань замало.
Так само, відразу видно, що це завдання можна вирішувати рекурсивним перебором, але теж не зміг скласти правильний алгоритм вирішення.
Хотілося б отримати пораду про те, яку літературу або статті почитати, для розуміння таких завдань.
А так же пропозиції про те, як вирішувати задачу сабжа.
Мої спроби закінчилися провалом.
Найкраще до чого я прийшов в теорії, це подібність рекурсивного алгоритму: habrastorage.org/files/82b/160/5cc/82b1605cc82b414.
(Кожна драбинка зменшується з кінця на 1 кубик, і розглядається "відрубана" частина)
Десь натрапив на неймовірно красиве рішення на Java, переписав його на C ++, але для мене це абсолютно магія, можливо хтось пояснить, що тут відбувається, і на яку базу все це спирається: pastebin.com/6ACsC9ta
Вирішити задачу легко - заводите масив 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 кубик (їх ми залишаємо без зміни), додати сходи з ji кубиків з нижнім рядом не довше, ніж i-1 кубик (до них ми додамо ряд з i кубиків). Що і робиться у внутрішньому циклі.
Намагаюся розібрати і закодіть ваше рішення, але не розумію.
питання:
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?
Загалом, потрібен ще більш детальний розбір.