Числа Белла — научитесь строить треугольник Белла | учебник по динамическому программированию

Описание: Для решения задач разбиения множества необходимо знать концепцию чисел Белла.

Очевидный вопрос: что такое числа Белла?

Число Белла B(n) показывает количество возможных способов разбиения множества из N целых чисел.

Ниже представлен классический список чисел Белла:

1, 1, 2, 5, 15, 52, 203 и так далее.

Давайте разберём этот список чисел Белла.
Здесь B0=1 (всегда равно 1).

B1=1 (это означает, что если есть одно целое число, то единственный возможный способ его разбиения — это 1).

B2=2, это означает, что возможных способов разбиения множества из 2 целых чисел — 2.
Например, рассмотрим следующее множество:

{1,2}
Возможные способы разбиения указанного множества:

[{1},{2}] и [{1,2}]

Аналогично, если в множестве {1,2,3} есть 3 целых числа, ряд чисел Белла показывает, что возможных способов разбиения множества — 5.

Числа Белла очень важны для решения задач разбиения и парных задач, таких как задача о парных задачах «Друзья».
При построении алгоритмов разбиения числа Белла являются неотъемлемой частью. Программирование и алгоритмы идут рука об руку.

Без концепции чисел Белла в центре невозможно написать несколько программ, решающих задачи разбиения, даже при использовании метода динамического программирования.

Это видео — первое из трёх видео в серии уроков по динамическому программированию от Джоуи. В этом видео я покажу, как построить треугольник колокола.

Используя треугольник колокола, вы можете легко определить список чисел колокола.

Построить треугольник колокола несложно. На самом деле, это увлекательно, и вы легко справитесь с этим, используя динамическое программирование.

Если вы хорошо изучите числа колокола, то освоите задачу о парном расположении друзей, которую я считаю одной из самых интересных задач динамического программирования для начинающих.

Всё, что вам нужно сделать, — это посмотреть это видео до конца.

Задача выравнивания текста: динамическое программирование
   • Step by step guide to solve text justifica...  

Задача укладки ящиков: динамическое программирование
   • Box stacking problem using dynamic program...  

Задача о сумме подмножеств: динамическое программирование
   • Subset sum problem | Tutorial on dynamic p...