Задача с контеста Яндекс
Вам на вход даются два числа n, h. (1 <= n <= 100), (1 <= h <= 10**18)
Равновероятно выбирается перестановка p = [1, 2, 3, ..., n], и строится декартовое дерево из пар (1, p[1]), (2, p[2]), ..., (n, p[n]). Определить вероятность того, что высота дерева равна h.

Напомним определение декартового дерева:
Декартовое дерево - это бинарное дерево, в узлах которого хранятся пары (x, y), где x - это ключ, а y - это приоритет.
Оно является двоичным деревом поиска по x и кучей по y.

Например n = 3, h = 2.
Рассмотрим все возможные пары от перестановки p.
(1, 1), (2, 2), (3, 3)
(1, 1), (2, 3), (3, 2)
(1, 3), (2, 2), (3, 1)
(1, 2), (2, 1), (3, 3)
(1, 3), (2, 1), (3, 2)
(1, 2), (2, 3), (3, 2)
Высота дереве 2 достигается для
(1, 1), (2, 2), (3, 3)
(1, 3), (2, 2), (3, 1)
(1, 2), (2, 1), (3, 3)
(1, 3), (2, 1), (3, 2)
Ответ 4/6 = 0.666.


Решение.
Заметим, что для h >= n, ответ 0.
Решать будет задачу динамическим программированием по подотрезкам.
Пусть dp[n][h] - вероятность, что в дереве с перестановкой длины n высота будет h.
Базой дп очевидно dp[0][0] = dp[1][0] = 1
Как посчитать dp[n][h], если мы уже для более меньших n и h уже посчитали дп ?

Чтобы обновить дп мы должны понять в какую позицию мы поставим максимальное число, так как это число будет корнем. Давайте переберем позицию в которую поставим максимум, пусть эта позиция 1 <= pos <= n, вероятность, что максимальное число попадет на позицию pos, равно 1/n.
Что вы можете сказать теперь про p[1], p[2], ..., p[pos - 1] и p[pos + 1], p[pos + 2], ..., p[n] ?
Первый набор попадете в левую часть дерева, а вторая в правую часть дерева.
Нам необходимо, чтобы в одной из частей высота была равна h -1. Пусть в левой части высота h - 1, тогда в правой части высота может быть любой. Получаем dp[n][h] += (dp[pos - 1][h - 1] * dp[n - pos][j] ) / n где j перебирается от 0 до h - 1.
Теперь наоборот рассмотрим случай когда в правой части высота равна h - 1, а в высота левой части любая.
Полуем аналогичное обновление dp[n][h] += (dp[pos - 1][j] * dp[n - pos][h - 1]) / n, где j перебирается от 0 до h - 1.
Заметим, что мы два раза посчитали dp[pos - 1][h - 1] * dp[n - pos][h - 1], следовательно не забудем сделать
dp[n][h] -= dp[pos - 1][h - 1] * dp[n - pos][h - 1].

Как мы видим наше решение работает за O(n^2 * h^2).
Давайте оптимизируем до O(n^2 * h).
Обратите внимание " dp[n][h] += (dp[pos - 1][h - 1] * dp[n - pos][j] ) / n где j перебирается от 0 до h - 1. "
Нужно ли нам перебирать j ?
Мы же могли заранее запомнить сумму dp[n - pos][0] + dp[n - pos][1] + ... + dp[n - pos][h - 1] = sum и не перебирать j.
Следовательно время работы O(n^2 * h).
Псевдокод в комментариях.