Как да се създаде алгоритъм за решаване на проблема в часа, или рекурсивно (проблемът на стълбата)

  • програмиране
  • математика
  • C ++
  • алгоритми
  • олимпиада по програмиране

Как да се създаде алгоритъм за решаване на проблема в часа, или рекурсивно (проблемът на стълбата)

Четох, че тези проблеми се решават чрез така наречения "динамично програмиране", но за съжаление, макар да разбере същността на този метод, умения ollimpiadnyh решения на проблеми, не е достатъчно.

Както е добре, може да се види, че този проблем може да бъде решен чрез рекурсивно търсене, но също така и не успя да направи правилния алгоритъм решение.

Бих искал да получите съвети за какви книги или статии четат, за да разбере такива проблеми.
Както и предложения за това как да се реши проблема на субекта.

Опитите ми се провалили.
Най-добре е това, което дойде на теория, това сходство рекурсивни алгоритми: habrastorage.org/files/82b/160/5cc/82b1605cc82b414.
(Всяка стълба намалява от края на една матрица, и се счита за "отрязани" част)

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

За решаване на проблема лесно - манивела масив [N, N], във всяка клетка на [К, М], която е записано числото на стълби на блоковете K, долния слой от които се състои от М блокове. Броят ще бъде ненулева когато М <= K <= M*(M+1)/2.
Масивът е изпълнен с изходния шев К = 1 с формула А [K, M] = сума (А [К-M, R], R = 1..M-1). Размер на елементи в реда К = N е желания номер.

В решението на връзката, към която сте дали последователно изчислява броя на стълби от к кубчета, най-долния ред, което е не по-дълъг, отколкото аз блокове. За да намерите този номер, че е необходимо да са намерили по стълбите, най-долния ред са не по-дълъг от куба на I-1 (което ние не променя), добавете стълби СИ кубчета с долен ред не повече от I-1 куб (за тях ние аз ще добавя няколко зара). Което е направено във вътрешния контур.

Опитвам се да се разбере и да се код вашето решение, но не разбирам.
въпроси:
1) Как да стигна до това решение? (Какво да се чете?)
2) От това условие: М <= K <= M*(M+1)/2
3) В този случай, А [K, M] = сума (А [К-M, R], R = 1..M-1), както ще бъде M?
4) Array индексирани от 0 или 1?

Като цяло, трябва да имате по-подробен анализ.