Как эффективно подсчитать количество способов выбрать k элементов из n доступных.
Математика
Биномиальные коэффициенты имеют дело с вопросами типа «n выбирают k» = сколькими способами я могу выбрать k элементов из n доступных?.
Например, сколькими способами мы можем выбрать 4 различных числа из первых 10 натуральных чисел? Ну, это то же самое, что попросить 10 выбрать 4, то есть 210.
Формула для расчета биномиальных коэффициентов:
От математики к коду
Оказывается, хотя у нас есть уравнение в замкнутой форме (обычно оно действительно хорошее и имеет O(1)), факториал слишком дорог: в некоторых задачах мы не можем позволить себе хранить результат n!, заключающийся в том, что он может достигать абсурдных сумм, которые намного превышают тип long long.
Однако DP снова спасает нас: несмотря на то, что факториал нельзя сохранить, биномиальный коэффициент (n,k) можно легко сохранить в большинстве случаев, поскольку он обычно меньше. Например, 100 выберите 4 — это 3921225, но если мы хотим рассчитать это по приведенной выше формуле, нам нужно сначала найти 100! = 9,33x10¹⁵⁷, что в 9,8x10⁵⁹ раз больше, чем количество галактик в наблюдаемой Вселенной.
Подзадача:
DP(N,K) = количество способов выбрать K из N
Операции по подзадаче:
- это базовый случай?: если K = N или K = 0, результат, естественно, равен 1.
- если нет, то DP(N,K) = DP(N-1,K-1)+DP(N-1,K): количество комбинаций, учитывающих только элементы N-1 + комбинации, если мы уже взяли один элемент.
Выполнение
С учетом предыдущих концепций реализация проста:
