How to make an algorithm for solving a problem on DP or Recursion (Task on a ladder)?

Question

Programming

I read that such problems are solved by the so-called "Dynamic Programming", but unfortunately, although I understand the essence of this method, the skill of solving Olympiad problems is not enough.
Also, it is immediately clear that this problem can be solved by recursive enumeration, but also could not compose the correct solution algorithm.
I would like to get advice on what literature or articles to read in order to understand such tasks.
As well as suggestions on how to solve the problem of the subject.
My attempts ended in failure.
The best thing I came up with in theory is a kind of recursive algorithm: habrastorage.org/files/82b/160/5cc/82b1605cc82b414...
(Each ladder is reduced from the end by 1 cube, and the "chopped off" part is considered)
But this method led me to a dead end already on 13 cubes:
habrastorage.org/files/cf9/610/866/cf96108666db4ad...
My code: pastebin.com/XWE3QZgL
Somewhere I came across an incredibly beautiful solution in Java, rewrote it to C++, but for me it's absolute magic, maybe someone will explain what's going on here, and on what basis it all relies: pastebin.com/6ACsC9ta

Answer 1

Solving the problem is easy - create an array A[N,N], in each cell [K,M] of which the number of ladders of K cubes will be written, the bottom layer of which consists of M cubes. The number will be nonzero when M <= K <= M*(M+1)/2.
The array is filled starting from the line K=1 according to the formula A[K,M]=sum(A[KM,r],r=1..M-1). The sum of the elements in the line K=N will be the desired number.
The solution you linked to calculates sequentially the number of stairs of j cubes whose bottom row is no longer than i cubes. To find this number, it is necessary to add to the stairs already found, the bottom row of which is no longer than i-1 cube (we leave them unchanged), add stairs of ji cubes with the bottom row no longer than i-1 cube (to them we add a row of i cubes). This is what is done in the inner loop.

Answer 2

I could be wrong, but the problem is even easier.

main(x) {
    result = 1;
    for(i = 1; i < x/2; i++) {
        result += main(i);  // при x = 7, i = 1, 2, 3
    }
    return (x < 1) ? 0 : result;
}

A little explanation.
The number 7 can be decomposed like this:

0000000

0
000000

00
00000

000
0000

We don't need the rest.
Remember how the factorial is calculated.

f (x) {
  return (!x) ? 1 : x * f(x - 1);
}

As a result, we decompose the top row into even smaller ones and summarize the results.
The result for two is equal to the result of one,
for three the result is one. (an integer from 3/2),
for a four the result is one and the result is two, and so on ...
PS
The problem is interesting. Mrrl described one of the solutions
. I'm not 100% sure of my solution, but it seems to work :)