Необходимо объяснение работы кода и алгоритма

Question

Всем привет! Внизу я прикрепил пример кода написанный на python, я совсем не понимаю как он работает, пожалуйста, помогите с пониманием. Безумно буду благодарен за помощь!

k = 3 # сколько требуется выбрать животных
m = 4 # число видов
n = [2, 1, 1, 1]
total = 0 # число способов (результат)

def cnk(n, k):
  if k > n:
    return 0

  if n == k:
    return 1

  if k == 1:
    return n

  return cnk(n - 1, k - 1) + cnk(n - 1, k)

for i in range(0, len(n)):
  total += cnk(m - 1 - i, k - 1) * n[i]

print(total)

Answer 1

данный код определяет сколько способов существует для того, чтобы выбрать 3 животных из списка животных

в данном случае:

AA
B
C
D

можно выбрать

AAB, AAC, AAD, ABC, ABD, ACD, BCD

т.е. 7 разных варианта

по сути для каждого животного вычисляется кол-во сочетаний с другими животными и все складывается, получается

Answer 2

k = 3 # сколько требуется выбрать животных
m = 4 # число видов
n = [2, 1, 1, 1]
total = 0 # число способов (результат)

def cnk(n, k):
  if k > n:
    return 0  # базовый случай

  if n == k:
    return 1 # базовый случай

  if k == 1:
    return n # базовый случай

  return cnk(n - 1, k - 1) + cnk(n - 1, k) # тут 2 рекурсии их результаты складываются

for i in range(len(n)): # тут изменил но это тоже самое отсчет с 0 по умолчанию
  total += cnk(m - 1 - i, k - 1) * n[i]  # накапливаем результат
print(total)

Что конкретно код высчитывает я не знаю но это динамическое программирование. Использованы рекурсивные вызовы (функция вызывает сама себя) базовые случаи нужны для того чтобы алгоритм не зациклился и формируют простейшее решение задачи которое динамически усложняется.

Про динамическое программирование:

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

Поэтому ДП предлагает следующее:

Берем одну подзадачу с переменной X1, об остальных подзадачах пока забываем.
После того, как найдем оптимальное решение для первой подзадачи, берем подзадачу для двух переменных Х1 и Х2, и решаем ее с помощью уже найденного решения для первой подзадачи.
Получаем оптимальноерешение уже для большей подзадачи, где фигурируют переменные Х1 и Х2. Затем, используя полученное решение, берем подзадачи, охватывающиеX1,X2 и Х3.
И так продолжаем пока не получим оптимальноерешение для всей общей задачи.

Таким образом, для решения поставленной задачи методом динамического программирования необходимо:

разбить задачу на отдельные части (подзадачи, этапы);
определить начальные условия;
решить этиподзадачи;
объединитьэти решенияв одно общее решение.

БЛОГ НА HUSL

Необходимо объяснение работы кода и алгоритма

Ответы (2 шт):