Реально на PHP? Это не очень алгоритмический язык, он затачивался под строки, но если очень надо, пишите…
Алгоритм примерно такой (самый простой в объяснении) :
Использовать матрицу A(M, N) - количество лесенок из N кубиков, когда в основании M.
По понятным причинам M < N, то есть матрица треугольная.
Первое значение A(1, 2) = 1.
Далее имея треугольник A(M, N) нужно конструировать A(i, N+1) i=1…N
Тут вложенный цикл, так как нужно перебрать по одному весь второй ряд от j=1…(N+1-i) накапливая количество:
-- если j >= i то пропускаем это j (это не лесенка)
-- иначе проверим, что осталось от k=(N+1-i)-j - это на 3ий и выше этажи
----k=0 - количество = количество + 1 (тут нельзя использовать A - лесенка низковата)
----k>0 - количество = количество + A(j, k+j)
A(i, N+1) = количество
ЗЫ
Допускаю, что где-то обсчитался, решал эту задачу более 10 лет назад.
Причём решал не через матрицу, а рекурсией, просто с матрицей проще отлаживать.
Но всё было как-то так.
ЗЗЫ
Это вообще-то олимпиадная школьная задачка.