Задача из Собеседования в Google на Динамическое Программирование: Количество Уникальных Путей

Классический пример применения динамического программирования для ускорения работы рекурсивной функции.
Различные вариации этой задачи часто спрашивают на собеседовании в Google, Amazon и Facebook.

[СашаСЮтуба]

Это простая задача, вот у нас на заводе, начальник цеха ставит задачу
- Сделать дох3я из них3я и еще премии лишает если не выйдет. О как!

[Ingvar_konge]

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

[iskatoysen]

мне кажется что проще подойти к задаче с точки зрения вероятностей, любой путь будет содержать (n -1) шагов направо и (m-1) шагов вверх, тогда надо просто посчитать количество их возможных комбинаций, для n=5 и m=4, тогда решением будет (4 + 3)!/(4!*3!) = 35 вариантов. сложность такого алгоритма O(1).
Пояснения: (4 + 3)! это количество возможных уникальных вариантов если каждый шаг уникален, но у нас есть есть однотипные неуникальные серии шагов которые сокращают это количество, 4 одинаковых шага сокращают количество комбинаций в 4! раза, и другие 3 одинаковых шага сокращают в 3! раза.

[iGavelyuk]

Завтра на всех галерах страны за 200$ в месяц будут спрашивать о Динамическом Программировании. Мне особенно нравится, когда сидит "Байкер" часный предпрениматель и спрашивает "Что вы знаете о культуре нашей компании". Автору спасибо за видео.

[alexeys]

Стоит еще упомянуть, что в первом случае затраты памяти - O(1), а вот во 2 случае - O(n*m) (в конце алгоритма у нас в памяти будет вся матрица), и это в обоих случаях без учета затрат памяти на рекурсивные вызовы. Притом, можно улучшить затраты памяти до n:
1) Пишем итеративный цикл с проходом по строкам слева направо.
2) Не трудно заметить, что для вычисления очередной клетки, весь массив нам не нужен, а нужна только предыдущая строка, которую мы вычисляем на предыдущем шаге итерации, и клетка слева, которая также уже вычислена.

[Leonard_Gray]

Я не смог досмотреть это видео, просто потому, что у меня начались "вьетнамские флэшбэки" с сотен собеседований, где задавали крайне полезные и актуальные вопросы, которые я точно должен уметь решать.
"Где Вы видите себя через 5 лет?" да в вашем офисе буду бумажки перебирать, где ж ещё?!

[Utars]

Можно комбинаторикой: пусть a - количество ходов вверх ИЛИ вправо (неважно), b - общее количество ходов. Тогда ответ на задачу равен C из b по a

[learpcss]

очень доходчивое и наглядное объяснение, спасибо! с меня подписка! (пришел с гугл рекламы). Так же стоило упомянуть комбинаторное решение. Нужно будет посчитать количество перестановок вверх (их m-1, если m - высота поля), и вправо (аналогично n-1).

[sago]

Как уже упомянуло несколько людей в комментариях задача действительно может решаться просто по формуле, но если использовать рекурсию как в видео, то более простым вариантом пожалуй будет это:
int paths(int n, int m) {
if(n == 1 || m ==1)
return 1;
return paths(n-1, m) + paths(n, m-1);
}
Если точка находится на одной линии с роботом, то очевидно только один путь к ней, поэтому возвращает единицу, таким образом выход за рамки поля невозможен, и считать его не надо, такая рекурсия как по мне выглядит намного проще, да и для прямого пути в 5 клеток не надо будет вызывать 5 функций пока они не дойдут до робота, а сразу возвращает единицу.

[ЕвгенияТрамп]

Саша, здравствуйте! А вы будете продолжать вести канал? Сейчас очень актуальны ваши ролики с задачами и теорией (если она планируется), все очень доходчиво и понятно, спасибо!

[firejvlz]

хз как я сюда попал, но в принципе не обязательно уходить за границы матрицы - можно упростить дно рекурсии `if (n == 1 || m == 1) return 1;`

[unformedvoid]

Спасибо, полезно. Мне очень помогает знать простую идею, стоящую за алгоритмом. Потом очень легко распространить её на более сложные варианты.

[dorokhovea]

После твоего душевного рассказа на нашем собеседовании, я бы перевернул твой рисунок на 180 градусов, увидел твои округлившиеся глаза и сказал - спасибо, что пришел, пригласи пожалуйста следующего!

[АлександрДёмин-юъ]

Динамическое программирование - это не только запоминание промежуточных результатов, но также и само рекурсивное решение. Также как при вычислении числа Фибоначчи, данную задачу можно решить как простым циклом, так и рекурсивно. И именно рекурсивное решение с запоминанием промежуточных результатов является динамическим программированием для обоих задач.

[evgeniym]

Путь однозначно задается как n - 1 стрелка вправо и m - 1 стрелка вверх, выпишем стрелки в ряд в произвольном порядке (всего в ряду n + m - 2 стрелок). Тогда число способов расставить здесь n - 1 стрелку вправо равно количеству сочетаний из n + m - 2 по n - 1 (или по m - 1, что тоже самое). Ответ: (n+m-2)! / (m - 1)! / (n-1)!

[etaraba]

Если я не ошибаюсь, то можно без рекурсии намного проще. Нужно в каждой клетке (i, j) просчитать к-во вариантов. Начинаем с нижнего ряда слева направо - все единицы (т.к. снизу клеток нет, а слева все время 1). Начитая со второго ряда снизу значение К(i, j) = значение клетки слева К(i-1, j) (для клетки К(1, j) будет 1) + K(i, j-1). И так, пока не дойдем до точки К(n, m)

[JonnyToHell]

Отличный ролик!
6:55 мемоизация, спасибо )

[GrAlUnrealEngine]

И че я сюда зашел? Почуствовал себя тупым и пошел дальше 🤓

[Aneugene]

Спасибо большое! Стопнул на 1:02 и решил самостоятельно, после чего сверился. Советую всем так делать, хотя бы устно, в уме.

Можно, кстати, оптимизировать использование ОЗУ чуть меньше, чем в 2 раза. Это задача на внимательность, на нахождение треугольника паскаля в ней. А прелестное свойство треугольника паскаля - его симметричность, нам достаточно хранить его половину вместе с главной диагональю (для реализации подсказка: arr[n][m] считается как обычно, arr[n-1][m]+arr[n][m-1], а главная диагональ - arr[n][n] = arr[n][n-1] * 2).

[nurmuhammetsoyunov]

Если в задании нельзя использавать комбинаторику (хотя этот способ самый лучший) можносделать программу ещё проше,
На языке паскаль:
for i:=1 to n do a[i, 1]:=i;
for i:=1 to m do a[1, i]:=i;
for i:=2 to n do
for j:=2 to m do
a[i, j]:=a[i, j-1]+a[i-1, j];
write(a[n, m]);

Да уж, уже подзабыл программирование со школьных лет не занимался