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

Классический пример применения динамического программирования для ускорения работы рекурсивной функции.
Различные вариации этой задачи часто спрашивают на собеседовании в Google, Amazon и Facebook.
Эта задача на LeetCode: leetcode.com/problems/unique-...

[@sashalukin]

Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin

[@user-om3nc2up5p]

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

[@ovsyannikovo]

Cрочно пришлите нам его телефон! (Директор Гугля)

[@apristen]

Когда начальник требует "дох3я из них3я" очень важно убедить что "нах3й нужно" и таки получить премию! Вам просто не хватает навыков убеждения! :-D

[@user-bk1jk4wh3w]

Я в таких случаях начальнику всегда напоминаю один анекдот: Василий Иванович и Петька терпят крушение, и тут начинается диалог: -Петька приборы? - Двести - Что двести? - А что приборы? Так что умейте добиваться информации от кого либо.... в том числе и постановки задач по SMART.

[@user-ug4jp7ck2x]

Можно начать с заказа сырья у поставщика: дох3я килограммов самого чистого них3я. Можно даже сказать, что поставщик готов подождать с оплатой суммы в дох3я рублей, пока кладовщик примет заказ. Думаю на этом всё и закончится.

[@user-bk1jk4wh3w]

@@user-ug4jp7ck2x А потом сказать что поставщик оказался липовый, или банкротство объявил, в результате чего мы получим то самое нихЗя и как следствие дохЗя проблем. Задание выполнено))

[@iskatoysen]

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

[@maksymkoiev8824]

Вы написали мои мысли :)

[@Maksim_C]

быть может с точки зрения комбинаторики?

[@iskatoysen]

@@Maksim_C ну да скорее комбинаторика, есл угодно

[@chichkan87]

Все так, только сложность условно константная, все-таки, т.к. факториал не считается за константу, если нет заранее просчитанной таблицы готовых значений. А так получается О(n+m).

[@t3chcat613]

это всё хорошо в самом простом идеальном случае, который описан в видео. давайте выберем несколько клеток посреди поля и запретим через них ходить. или добавим условия, что из некоторых клеток можно ходить только вверх, а из некоторых - только вправо. или добавим веса при прохождении через клетки. алгоритм, описанный в видео, продолжит работать, с минимальными доработками.

[@unformedvoid2223]

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

[@NightFrostDevil]

Александр, прекрасно объясняете, спасибо!

[@AWoh51EIbvdf]

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

[@AWoh51EIbvd]

@DaXz на самом деле видел тех кто пол года бесплатно работал, ради того чтоб начать и получить хоть какоето резюме.

[@AWoh51EIbvd]

@DaXz стажеры каторые работают 8 часов в сутки. Нет это джуны. Там были реальные работы и реальные требования.

[@AWoh51EIbvd]

@Руслан Грищук пол украины так работает, от дизайнеров до фулстакеров. Я рад что вы в розовой зоне и у вас все хорошо.

[@AWoh51EIbvdf]

@Руслан Грищук Могу сказать тоже про наши компании - только лох не нанимает скиловых людей за копейки а ищут нинзь и фей, а потом собирают команду сказочных дол№оебов и такие - раньше мы брали с опытом 7 лет надо повысить планку хотябы в трое. А потом ХРМ пишет тебе нам нужен чел с опытом Вью не менее 20 лет - браво!

[@denisdragomirik]

@@AWoh51EIbvd половина компаній України, які працюють на ринок України. Але у нас 90% айті - це аутсорс, або стабільні продуктові компанії.

[@alexeys1789]

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

[@user-fo6dm5gy8e]

В первом случае сложность для памяти не O(1), каждый вызов ф-ии это новый элемент в памяти

[@alexeys1789]

@@user-fo6dm5gy8e внимательно читаем сообщение еще раз и что мы видим??? "это в обоих случаях без учета затрат памяти на рекурсивные вызовы"

[@volervagashim]

​@@alexeys1789после чего на собеседовании идём лесом, ибо затраты на рекурсию тоже всегда надо учитывать, иначе это ошибка. Стек растет пропорционально глубине рекурсии

[@alexeys1789]

@@volervagashim ахахахах, если это рофл, то харош))0

[@volervagashim]

@@alexeys1789 поясни, плз, видимо я не понимаю чего-то

[@user-jq8lx7ge7f]

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

[@nikitafamily5341]

Очень круто объясняешь! Посмотрел не отрываясь, спасибо!!!

[@Ingvar_konge]

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

[@user-vu6hn4ul2i]

Ну че там, как дела?

[@revingar]

​@@user-vu6hn4ul2i, видимо закончил

[@axiswait5339]

Выучи язык, а эти задачи можно только запоминать и выписывать. Подход, сейчас решу сам за часок из головы, тут только сломает тебя. Просто найди готовое решение , пойми его, запомни и иди на новую задачу.

[@vb7038]

​@@axiswait5339можешь подробнее расписать свою точку зрения?

[@user-wt9bn3fh1l]

🤣 Мужик, я не знаю учишь до сих пор программирование или нет, но с юмором у тебя однозначно все в полном порядке 😅

[@sago6542]

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

[@JonnyToHell]

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

[@scruper]

Александр. Спасибо. Наткнулся случайно. Прекрасный материал и его подача. Не останавливайтесь!

[@Leonard_Gray]

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

[@AWoh51EIbvdf]

Я ща на старости флешбеки как фильмы смотрю, сьэкономил на кинотеатрах и купил клей момент и ласты, перед сном надеваю на всякий случай и наслаждаюсь 5Д без искуственного интелекта, последних технологий, промисов и блокчейнов. Замомните - То что нас не убивает, н№XeRa не делает нас сильнее, просто убивает потом.

[@Utars]

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

[@vDungeon]

Воот! Думал ровно про то же самое. Тут хватит одной формулы без циклов.

[@lapawarlord]

Звучит логично, но не совсем понятно)

[@levonagazaryan9391]

А тк надо посчитать побыстрее, то воспользуемся асимптотикой сочетаний через экспоненту - это и будет примерный ответ, который можно посчитать аж за lon (n + m))

[@leonovgleb8535]

Сначала посчитал рекурсией (правда, немного другой), потом подумал - а почему нельзя аналитически решить? Получил тот же ответ, что и вы: Выборка из (m+n-2) по (m-1). Или, что то же самое, выборка из (m+n-2) по (n-1). Или, ответ = (m+n-2)!/{(m-1)!*(n-1)!}

[@apristen]

Видео как бы "обосновывает" применение сильных сторон компьютера, а вы поднимаете вопрос силы человеческого мозга. Ну да, если кончится бензин кругом - те кто быстрее и дольше могут бегать будут в выигрыше, но как правило человек (и даже дедуля и даже ребёнок) используя машину становится сразу быстрее бегуна, причём (и это самое главное!) НЕ заморачиваясь на проблеме, а решая задачу. Это видео ценно как раз тем, что показано как использовать силу (преимущество) компьютера, который может и не оптимально (как человек оптимально - аналитически) решит задачу, но целый _класс_ задач зато где надо "быстро смоделировать" (рекурсией - тут силён комп конечно) не заморачиваясь.

[@user-oz1nq6vt8m]

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

[@Aimilomim]

Есть видео, (Тимофей Хирьянов "Динамическое программирование сверху и снизу"). Смотрел его через пару дней после этого видео. Обычно можно переделать рекурсию на цикл и это улучшает производительность.

[@ConstantinKubrakov]

Для обЕих задач

[@karfagen86]

Грамотно объяснил, спасибо!

[@learpcss9569]

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

[@sashalukin]

Спасибо! Действительно, так можно и это очень красивое решение. Но решил не перегружать это видео.

[@cdeblog]

@@sashalukin очень зря, это наиболее простое и красивые решение)

[@antonpetrenko9176]

@@sashalukin, не перегружать видео и поэтому там 8 мин абстракных размышлени, не самый очевидный алгорим, и избыточная реализация решения.. На работу звяли?

[@user-vn7ys1ui6h]

@@sashalukin а ответ в большой таблице равен 35?

[@leonovgleb8535]

Нашёл его же, загнал в код. Получил не ожидаемую мной особенность: при больших значениях m и n факториалы легко вылетают даже за границы лонг инта, т.е. требуется правильно выделять память. А вот метод с вспомогательной таблицей менее требователен в этом конкретном аспекте. P.S. А проще и элегантнее всего задача кодится заполнением аналогичного массива из исходного угла в конченый. Можно заполнять "полосками". В первой колонке все единички, в первой полоске тоже единички, а в каждой клетке потом - сумма соседей снизу и слева. Так полоска за полоской и заполняем. И кодить просто (рекурсии-то нет), и цифирки не большие. И особенно пикантно то, что если вычисления большие и их надо "на паузу" ставить, то запоминать надо самый минимум: текущее состояние массива и координаты последней заполненной клетки.

[@iwanttobealihgt]

спасибо за видео, очень помогло!

[@evgeniym9134]

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

[@Aneugene]

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

[@aleksandrzhadetsky2535]

спасибо за разьяснение

[@somestrangeperson]

Спасибо, за понятное объяснение, лайк!

[@alexandergavrilov8019]

Спасибо, интересный разбор.

[@firejvlz]

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

[@evgeniibubolev9881]

а если n уже равно 1, а m ещё нет? У нас же остаются еще куча вариантов развития событий

[@firejvlz]

@@evgeniibubolev9881 нет, не остаются - возможен только один путь по прямой вдоль "стеночки"

[@evgeniibubolev9881]

@@firejvlz ох, спасибо, вы конечно правы

[@etaraba9385]

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

[@user-oz1nq6vt8m]

Да, можно прежде и левый столбец заполнить единицами. Однако это не динамическое программирование.

[@avshukan]

Плюсую

[@dfdghyuiopoiuhgvfghjo]

реально интересная задача!

[@Igril]

Для первой задачи ответ 4, но это так, придирка. Видос отличный!

[@rizhiy87]

4 - это если он вниз ходить умеет

[@Igril]

@@rizhiy87, вы правы, я упустил исходные требования, да, три варианта.

[@alexrbh9515]

интересная задачка, своеобразное комбо матрицы и дерева)

[@nikenuke]

спасибо!

[@nurmuhammetsoyunov3967]

Если в задании нельзя использавать комбинаторику (хотя этот способ самый лучший) можносделать программу ещё проше, На языке паскаль: 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]); Да уж, уже подзабыл программирование со школьных лет не занимался

[@dmitriifilimonovart]

Спасибо. Окончательно убедился что да ну его нафиг.

[@user-kv3eo9br8m]

изначально не понимал с какой стороны подойти к решению) В итоге пришел к решению с комбинаторикой. Но решение автора мне очень понравилось. Правда что рекурсия уже не подойдет на очень больших m и n

[@user-nm9gk6bf5z]

Можешь написать как это комбинаторикой решить?

[@nanoIX9]

Хороший ролик, хорошее объяснение. Мы задачи подобного рода аналитически решали на уроках информатики в 6-7 классах (не спец школа), на Basic. Сижу и думаю, то ли учитель хороший был, то ли что-то в мире поменялось. :)

[@ilnar129]

Сейчас аналогичная задача даётся в ЕГЭ, причём это не самая сложная

[@dorokhovea]

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

[@elel4823]

Добрый день. Можно ли решить задачу следующим способом? Робот может двигаться только вправо и вверх, т.е. каждая клетка из которой можно двинуться вправо или вверх является развилкой и дает +1 путь - это не крайние правые и не крайние верхние клетки. При поле размером 1 клетка в ширину или 1 клетка в высоту у робота только один путь. Т.о. получаем алгоритм: h=5; n=4; ways_count=1; hi=1; ni=1; for(hi=1;hi++;hi

[@avshukan]

Развилка даёт не +1 путь, а +к путей , где к - количество путей до этой клетки. Проверьте сами себя: посчитайте для квадрата 4*5 "руками" (должно получиться 35) и своим алгоритмом

[@mikepolo6734]

Можно еще оптимизировать вдвое, если учесть, что paths(n, m) === paths(m, n)

[@user-yf6tj3br7t]

Это жестко конечно

[@enott]

Это ж простейшая комбинаторика :)

[@freehck]

У меня только один вопрос: зачем решать перебором то, что считается аналитически? Роботу нужно сделать n движений вверх и m движений вправо. Вполне очевидно, что количество путей равно числу сочетаний из n+m по n.

[@denismaleev3848]

Решал такую задачу много лет назад на позицию джуна

[@redflower9323]

Все проще. Это треугольник паскаля. Время работы О(2*(m + n)) В случае если n>=2 и m >=2 ответ записывается формулой (n + m - 2)!/((m - 1)! * (n - 1)!) //просто найти факториалы отдельно и посчитать Иначе ответ 1

[@YevhenDiulin]

Можно увидеть в этом треугольник Паскаля. Номер ряда L = n + m - 2. Искомый член ряда P = Min(m, n) - 1 Результат L! / (P! * (L - P)!), то есть число сочетаний из элементов по Ну и всё, не нужно так заморачиваться. Дабы не мучить компьютер лишний раз, число сочетаний высчитываем как "Произведение P последних из L делить на P!" И тогда сложность из O(m+n) становится O(min(n, m)). Как бы сделать ещё красивее?

[@user-iq9ll8lz9m]

поле размером 2000 х 2000, с факториалом не мучать компьютер лишний раз не получится

[@YevhenDiulin]

@@user-iq9ll8lz9m Для компа перемножить тысячи чисел - десятая доля секунды. Надо, конечно, позаботиться об избежании переполнения, но всё равно это будет гораздо быстрее в сравнении с оббеганием 4 000 000 ячеек. К тому же у нас не растёт потребление по памяти, чего не скажешь про код автора.

[@freedomtv2295]

@@YevhenDiulin так а астмптотику подсчёта факториала вы знаете? Плюс следить за переполнением легко, но что делать если оно будет?(а оно будет) Длинная арифметика или варианты получше?) Все это красиво только на листочке, а на практике чёт не очень

[@YevhenDiulin]

@@freedomtv2295 Можно взять тип с плавающей точкой и не считать факториалы отдельно, а сразу считать число сочетаний: умножил на один член чеслителя, разделил на один член знаменателя, потом на другой член чеслителя и на другой член знаменателя. Есть пути в обход.

[@freedomtv2295]

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

[@Sergey-Primak]

матрица NxM число ходов вправо n=N-1, число ходов вверх m=M-1 нужно найти кол-во сочетаний n ходов вправо и m ходов вверх всего ходов s=n+m paths = s! / (n! * m!) = (s*s-1*s-2*...*s-n)/(1*2*3*...*n) = ИЛИ = (s*s-1*s-2*...*s-m)/(1*2*3*...*m) то есть выбираем меньшее из k=min(n, m) и вычисляем paths = s-i/(1+i), i=0..k-1

[@CyanideBtm]

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

[@igorlitvin1779]

вот легче решение для понимания. Если идем вправо на одну клетку тогда это приравниваем к 1 а если вверх то 0. Тогда получается бинарное число из 1 и 0. Нам надо что бы в этом бинарном числе было 4 единицы в любом порядке. Всего 7 цифр в нем. В первой задече получается бинарное число из 3х цифр в котором должен длжно быть одна единица в любом порядке. Таким образом можно решить эту задачу с любым колличеством клеток. Следовательно нам просто надо найти сколько бинарных числел с 7 знаками содержит 4 единицы. Код элементарный так же: def decimalToBinary(n): return bin(n).replace("0b", "") N=0 for i in range(int('1111111', 2)): if str(decimalToBinary(i)).count("1")==4: N+=1 print(N) 35 для последней задачи получаем и 3 для первой итд

[@BizzaroFukuro]

Это на самом деле задача из комбинаторики для 7-8 класса. Здесь можно даже увидеть треугольник Паскаля, который разворачивается направо-вверх: ... 1 ... 1 4 ... 1 3 6 ... 1 2 3 4 ... 1 1 1 1 1 ... Число в каждой клетке равно количеству маршрутов, ведущих в неё из начальной клетки. Ну и одновременно с этим, числа, из которых состоит треугольник Паскаля представляют собой кол-во сочетаний, поэтому ответ C из n по m.

[@pahom2]

Фишка в том что посчитать биномиальный коэффициент всё равно не просто, а если на машине умножение долгая операция то и без дополнительной памяти не обойтись

[@user-yd9xy3rb4x]

А вот и спасибо)

[@DeadBuddy01]

Как не программист сломал себе мозг пока додумался почему массив на единицу больше

[@fruktiliyagoda6555]

Я долго думал, что же мне напоминает ДП. Это как кэширование данных, чтобы не приходилось каждый раз обращаться к базе

[@andreycanon8929]

2001 год. У нас тогда появился компьютерный класс в школе и на информатике мы писали программу с похожим решением. Только там был не робот, а кенгуру.

[@maksimr3175]

Если кенгуру - тогда m-n заменяем на k-z . Только так и не как иначе!

[@A1bertG]

@@maksimr3175 а для черепашки x-y

[@maksimr3175]

@@A1bertG шуточки шутим?! Какие "ХУ"? Ну какие ху? Какие ху. Это элементарно ! Если черепашка значит n-z ! Шучу. Всех благ! Кидаю краба. Присел на корточки. Семечки плюю в кулёчек .

[@apristen]

Контент супер! _Динамическое программирование_ - способ решения сложных задач путём разбиения их на более простые подзадачи. Вся наша жизнь немножно динамическое программирование :-) Видео как бы намекает зачем компьютеру надо столько много памяти (на стек вызовов рекурсии, на массив для мемоизации) :-) Тут много людей пишет в комментариях, что можно решить оптимальнее и аналитически вообще (сведя к формуле), но если хорошенько подумать, то показана то не конкретная задача, а _класс_ задач. Ну и опять же, компьютер изобрели чтобы НЕ заморачиваться. Да, можно интеграл красиво аналитически посчитать, а можно методом трапеций численно. Аналитически это конечно же красиво и "интеллектуально элитно", но в суровой реальной жизни когда заказчику надо "вчера!" и результат нужен "прям щас и один раз!" и "уже всё!" и у директора дёргается от этого глаз от нервов всех этих - математика-аналитика-теоретика раньше уволят нафиг (и заводу может кирдык придёт), ну или премию дадут "Петровичу" который методом трапеций за 5 минут прикинул и сказал "ах**но! материала хватит! вот смета!" :-))))

[@akiiaev]

Разве математик-теоретик не посчитает интеграл по красоте сейчас 5минут?

[@apristen]

@@akiiaev математик-теоретик - товар штучный, а решения надо принимать много где, и тут на помощь придёт "числодробилка" которая сделает даже дурачка "великим математиком" ;-) в мире много рукожопов - поэтому изобрели санчала трафареты, а потом и ЧПУ станки, в мире много тугодумов - поэтому изобрели компы и численные методы и методы мат.моделирования. и это дало возможность даже дурачкам кормиться и размножаться, алилуйя! :-D но конечно же "для любителей помучаться" (мазохистов) остались ручные дрели, лобзики, логарифмические линейки, кульманы для чертежей вручную и прочие "орудия пыток" :-D но мне как-то нравится в 3D принтер или ЧПУ загружать чертёж, который я могу поправить в САПР если что не переделывая полностью. видимо я не дошёл до "дзена", мне результат как-то важнее процесса.

[@vryaboshapko]

Примерно в этом и заключается талант грамотного технического менеджера: отличать задачи, которые нужно решать быстро и в лоб, от тех, которые нужно решать долго и красиво. И в промышленной разработке, конечно, первых гораздо больше, но всё же не 100 %.

[@krotus84]

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

[@___p_y_c_u_4___470]

А вариант "змейкой" не учитывается? Или нужен кратчайший путь?

[@surekt4780]

0:25 . Робот не может ходить вниз, то есть вариант змейки не возможен в принципе

[@___p_y_c_u_4___470]

@@surekt4780 , да, я уже понял, просто не внимательно послушал условия.

[@vitall789]

Интересно кто это применил это на практике больше одного раза?

[@Tess7490]

У нас эта и подобные ей задачи были в 8 классе на уроках информатики. В Паскале писали всякие алгоритмы для роботов. Всегда ненавидел это дело. По сути, весь 8й и 9й класс были посвящены тому, чтобы робот бегал по карте с препятствиями и искал выход наиболее оптимальным образом. Вечно ошибался и либо написанная прога не работала, либо робот шёл не туда, куда надо, либо шел куда надо, но не оптимальным способом, либо учителю не нравился сам код... В общем, с программированием не сложилось :)

[@airn587]

у нас была "черепашка" и "робот-пылесос". робот нужно было программировать на русском. это был 6й класс и я обожал это дело, тогда и влюбился в программирование окончательно :)

[@diogen8443]

А у нас вообще не было компьютеров.

[@lone9724]

хм, почему путь 21 22 12 13 до двери не рассматривается? Почему учитывается только самый короткий путь?

[@Gregory-vc2vs]

Можно свести задачу к графу, построить матрицу смежности и возвести в степень k, где k - расстояние между вершинами. Это будет где-то (m*n)^2.5 сложность, зато потенциально найдет решение в общем лучае. + Будет задел на применение прочих графовских алгоритмов

[@alexanderpalagin4662]

Можно решить задачу через комбинаторику и найти ответ в одну строчку вычислений)

[@abcdefghi1489]

@@alexanderpalagin4662на больших m и n устанешь, эти факториалы не влезут в размер переменной, нужно будет с бубнами плясать, лучше загрузить процессор и точно знать, что оно выполнится, а не упадёт, потому что комп не сможет оперировать в формуле факториалом от миллиарда)

[@kikislav]

Эту задачу можно решить ещё быстрее увидев, что это треугольник паскаля, правда надо ещё знать формулу его. Тогда апроксимация времени работы алгоритма будет = О(n+m).

[@user-es7jg3qi8j]

Эту задачу можно решить и за константное время,, используя формулу количества сочетаний. Только для конкретно этого варианта задачи нужно уменьшить и ширину, и высоту сетки на 1.

[@user-dp6th8fx4w]

@@user-es7jg3qi8j Для количества сочетаний придётся считать факториалы, каждый из них считается за время O(n). Тогда для этой задачи О(max(n,m)).

[@kikislav]

@@user-dp6th8fx4w Там факториал от n+m

[@user-dp6th8fx4w]

@@kikislav Вы написали, и я задумался. Раз уж так, можем считать факториал с конца, то есть a*(a-1)*(a-2)*...*(a-i), где а=n+m в нашем случае, а i=min(n,m); попутно же будем считать количество перестановок (i факториал); поделим одно на другое и получим искомое количество сочетаний. Выходит что сложность алгоритма и того меньше - О(min(n,m)).

[@kikislav]

@@user-dp6th8fx4w На самом деле апроксимация вычисляется более сложным путём, так-как апроксимация умножение двух чисел длиной n и m равна O(max(m, n)) Вы можете сами проверить, написав программу, потому что компьютер умножает числа примерно как мы, в столбик.

[@dm_www9360]

Ох, ребята. Снимаю шляпу перед вами! Эта область для меня темный лес. Всегда вами восхищался!

[@Voprosik102]

Половина комментаторов пропустили важную часть условия и умничают. Всё, что нужно знать о комментаторах

[@volervagashim]

Можно обратить внимание, что это просто повернутый треугольник паскаля и решить задачу просто фомулой C из n по k, нет? Или я чего-то не догоняю?

[@GrAlUnrealEngine]

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

[@vitpvs8062]

вспомнил basic и fortran 4

[@ovsyannikovo]

и пошел дальше играть в видеоигры? )))

[@GrAlUnrealEngine]

@@ovsyannikovo а чего добился ты 😅, я вот много игр прошел - дибильных

[@ovsyannikovo]

@@GrAlUnrealEngine ну для начала я смог завязать с играми 🙂

[@GrAlUnrealEngine]

@@ovsyannikovo жаль тебя 😂 (рофлю), а меня в их разработку затянуло.

[@inmosh]

чётко

[@mrposeidon2813]

по моему задача решается легче математически. всего шагов n+m-2 и надо выбрать лишь номер шагов вверх или вправо, тоесть ответ С из n-1 по n+m-2 или C из m-1 по n+m-2 тут как удобнее, т.к. числа эти будут равны

[@tomahawk777]

Вроде все понятно и просто ,но если самостоятельно сделать ,я бы прикурил )

[@abylayamanbayev8403]

Можно решить задачу представив клетки в виде бинома Ньютона

[@user-td5rb5wd1m]

Почему у тебя так мало подписчиков я считаю то-что ты хороший блогер жилаю удачи и дальше

[@sashalukin]

Спасибо!

[@user-td5rb5wd1m]

Знаешь иногда я завидую таким как вы Веть у меня нет даже канала не то что подписчиков а ты можешь помочь нам

[@zelmanfeig5404]

@@user-td5rb5wd1m Ютуб - это развлекаловка, людям нужны котики и похабные анекдотики, никто не будет после работы динамическое программирование смотреть.

[@user-td5rb5wd1m]

@@zelmanfeig5404 и что?

[@user-td5rb5wd1m]

@@zelmanfeig5404 Я просто выразил свои мысли

[@Dmitry-mo1pt]

n, m = int(input()), int(input()) b = [] for i in range(n): b.append([0] * m) for i in range(m): b[0][i] = 1 for i in range(n): b[i][0] = 1 for i in range(1, n): for j in range(1, m): b[i][j] = b[i - 1][j] + b[i][j - 1] for i in b: print(i) Аналогичный алгоритм на питоне

[@pu0081]

Случайно, не воспользовалась ли майкрософт данной задачей для отбора программистов для написания windows 10 с критерием - кто решил данную задачу данным способом, берём, а кто другим способом - забраковали. Из чего такая аналогия? Когда комьютеры всё мощнее и мощнее, а работают всё медленнее и менее отзывчиво. По сути: функция О(...) не покрывает всех критериев затрат времени. Ещё есть затраты на вызов стека, дополнительное пространство памяти на хранениние результатов, пустые сравнения и копирование просчитанного значения в память и из памяти. Я вижу лучший путь, чем доп массив. Представленный автором 2й метод несколько быстрее первого, но не отличается принципиально. Спасибо за видео

[@user-ig2si9jw9z]

Уважаемый автор, на 5.52 сек клетка 31, говорит что там количество ходов 1 шт. А как же последовательность 11 - 12 - 22 - 21 - 31 ? Может условие чуть иное в задаче? получается что мах количество ходов для n=3 m=2 равно не 3 а 4. Спасибо

[@MuKeXa]

Кудой, кудою? По ТЗ робот может ходить лишь вправо и вверх.

[@user-tu9yu8zc9j]

Хороший контент, жаль что Саша канал забросил.

[@SANDRO_DEMOS]

Думаю лучше было бы использовать вместо робота монстра из корпорации монстров😄

[@andreikarpiouk9047]

Только функция 2^(m*n) - показательная, а не экспонента. Спасибо за видео!

[@user-sv8oq5wd3q]

Добрый день! Возможно, я чего-то не понимаю, но я вижу здесь классическую рекурсию. Да, есть двумерный массив состояний, но заполняется он в рекурсивной функции. Вся прелесть ДП, на мой взгляд, как раз в том, что рекуррентное соотношение обрабатывается в цикле без применения рекурсии.Я могу предложить свой вариант. Если я неправ, то прошу дать разъяснения.

[@user-qg2tn7lv4n]

Добрый день. Опишите пожалуйста свой вариант с заполнением массивов. Я учусь и интересно как это относительно данной задачи

[@denispetrovich3039]

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

[@airn587]

Почему цена алгоритма высока? Рекурсию необязательно реализовывать через вызов той же функции. В этой конкретной задачи решается массивом 2*M или 2*N.

[@denispetrovich3039]

@@airn587 да гдето читал, что рекурсивные функции норм так жрут А как делать не через функцию? через цикл с ветвлением?

[@user-bh3mm6ck4q]

Для m = 3, n = 3 проверь. По твоей формуле 5, по факту 6

[@denispetrovich3039]

@@airn587 ну и недавно посмотрел про рекурсии. Если они довольно большие - просто ловишь stackOverflow

[@denispetrovich3039]

@@user-bh3mm6ck4q блин) я уже не помню че там было)) Ну в целом я к тому, что не всегда нужно решать задачу, чтобы она решала любые вариации впоследующем. Если есть возможность сделать тупо и просто, потратив меньше часов и энергии, то, возможно, это лучшее решение. А если вдруг потом понадобится расширение - тогда уже подумать над алгоритмом. Опять же, зависит от котекста

[@user-hw3mz7hv7e]

У тех, кто не ищет лёгких путей, может быть ещё один путь: вверх, вправо, вниз, вправо, вверх.

[@user-jp8jl5mg3v]

Задача не на ДП, она бьётся формулой. Ясно, что будет сделан m + n -2 ход, из них n - 1 будет вверх. Легко понять, что число маршрутов равно числу способов выбрать из m + n - 2 мест под проход вверх ровно n-1, это сшка из математики. Такую ц-шку можно посчитать за линию (то есть О(m+n)), что быстрее дп, так как дп предполагает сложность O(m*n).

[@goldstein1]

На 8:12 можно проверять выражение на равенство нулю и возвращать значение из массива ниже Сэкономим целую строчку😅

[@Aimilomim]

Спасибо. Решение очень красивое и простое, но если вы ищите путь, то где препятствия? Если есть препятствия, то путь будет с шагами назад и вниз, а это может привести к циклам, которые можно исключить если на карте ставить метки, где идёт текущий прогон. Вы передаёте в рекурсивной функции параметр - таблицу, то есть таблица должна остаться в стеке при каждом вызове, но это при росте размера карты приведёт к ошибке Stack Overflow? Избежать ошибки можно если сделать "прямое" решение с поиском путей от первой точки, заменив рекурсию на цикл, а таблицу из параметров сделать переменной.

[@ukrainekiev3990]

Решение автора ролика не самое простое и далеко не самое красивое! ;) И ещё вы не внимательно слушали условие задачи - робот может ходить вверх или вправо, но он НЕ МОЖЕТ ходить вниз или влево!

[@Aimilomim]

@@ukrainekiev3990, вы серьёзно? Просто привычки программиста, ТЗ меняется на ХЗ в любой момент. В общем, можете рассказать пользователям чего робот "НЕ МОЖЕТ".

[@ukrainekiev3990]

@@Aimilomim, при чём здесь "можете рассказать пользователям"? Речь идёт о том, что вы НЕВНИМАТЕЛЬНЫЙ и невнимательно слушали условие задачи! Невнимательность это не привычка программиста, это привычка раздолбая, от сюда ваши кривые коды со всеми вытекающими ))

[@Aimilomim]

@@ukrainekiev3990, в хорошей программе должна быть возможность модификации. А у пользователей всегда есть новые требования. Вы считаете, что рекурсия лучше циклов? Параметры рекурсии не имеют значения?

[@seagray69]

@@Aimilomim забей. Он не поймёт

[@user-gc3lm8pi2v]

Разве функция хелпер типа может вернуть массив инт?

[@chillappreciator885]

Вообще не понял, как прийти к выводу что: paths(n, m) = paths(n - 1, m) + paths(n, m - 1)

[@Anton-dl7me]

мне кажется это потому что мы считаем число путей (комбинаций как прийти) к точке А и к точке В. Которые находятся либо слева либо снизу.

[@SuhininAlex]

Это просто разложение первого хода. Ты можешь пойти вверх и тогда высота оставшегося поля уменьшится на 1. Или ты можешь пойти вправо и тогда ширина поля уменьшиться на 1. Соответственно общее кол-во путей - это просто сумма путей для обоих вариантов.

[@alexeyivanov3222]

рекурсия это - зло (в большинстве случаев) всегда нужно быть ОЧЕНЬ осторожным с рекурсией (а лучше избегать ее), т.к. очень часто неизвестна глубина рекурсии и размер стека, а отсюда и до переполнения стека недалеко (если конечно современным прогерам известно что это такое :) )

[@MultiOpachki]

Это утверждение верно, если язык не поддерживает TCO и ленивые вычисления (если, конечно, противникам рекурсии известно что это такое :) )

[@alexeyivanov3222]

@@MultiOpachki противники рекурсии любят писать переносимый код, который не зависит от платформы, компилятора, настроек, ... :() кстати даже не хочу знать что такое ленивые вычисления, хотя догадываюсь зато хорошо знаю как сложно найти переполнение стека, которое происходит раз в 5 лет у одного юзера из 1000

[@MultiOpachki]

​@@alexeyivanov3222 Настолко переносимые, что эти программы запускаются еще и на AVR, например? Чтож, похвально.

[@toxic-text]

А сколько даётся времени на её решение?

[@adventurer_v]

Для относительно небольших размеров грида самым быстрым решением будет формула биномиальных коэффициентов, так по использованию памяти мы получим O(1)

[@Mike-hp3fh]

там формула еще проще

[@adventurer_v]

@Mike я не считал максимальный грид для моего решения, но для решения на литкоде мне хватило трёх переменных long long и небольшой оптимизации. В итоге самый быстрый результат на сайте.

[@avshukan]

Разве формула биноминальных коэффициентов даёт О(1). Там же, кажется, О(n)

[@adventurer_v]

@@avshukan ты не совсем прав, фактически нам нужна петля для подсчёта факториала, но при минимальном упрощении мы считаем только то колличество итераций, которое будет меньше (k!-1 Или (n-k)! -1)

[@avshukan]

@@adventurer_v ну, то есть O( min(k, n-k) ) в худшем случае, это О(n/2) так?

[@uuuummm9]

Всегда думал, что динамическое программирование это нечто крутое. А оказывается это просто кэш данных?

[@a.osethkin55]

Спасибо за мемоизацию

[@user-od8rp3gf2z]

так в МИРЭА на факультете РТС это же вроде на 1 курсе было....ну правдо 95 процентов людей купило зачет за 4 к......но сам факт.........

[@matanmaster]

Динамическое программирование здесь понадобилось бы, если бы были случайно разбросаны острова, которые бы случайно вырезали часть маршрутов. А в задаче именно в таком виде тут будет чисто комбинаторное решение в виде функции от m,n, равной числу сочетаний из (n + m - 2) по (n - 1) или (m - 1), без разницы

[@zugzug90]

Подскажите пожалуйста, как выводится такая формула и почему для данной задачи? Заранее спасибо.

[@matanmaster]

@@zugzug90 Оно не выводится, оно по смыслу есть) У тебя путь длиной n + m - 2 в котором ты делаешь (m -1) шагов вниз и (n - 1) шагов в сторону. Ну то есть условно можно представить путь как последовательность из 0 и 1 длиной (n + m - 2) в которой будет(n - 1) нулей и (m - 1) единиц, располагающихся в случайном порядке. Тогда совсем очевидно что количество таких перестановок будет числом сочетаний кол-ва нулей или единиц из всей длины

[@zugzug90]

@@matanmaster "ты делаешь (m -1) шагов вниз" - но ведь вниз ходить нельзя.. Все таки непонятно, как получается (n-m-2).. Мб (n + m - 2) ? Там и выше у вас такое число кстати. Комбинаторику уже совсем не помню, пока что утверждение для меня неочевидно, но вероятно если освежить в голове пару глав - станет понятно лично мне. В любом случае спасибо за разъяснения.

[@matanmaster]

@@zugzug90 Ну в данном ролике вверх, обычно в этой задаче идут из верхнего левого в нижний правый. (n - m - 2) и нет нигде, там сумма.

[@likalucky]

Пока такие задачи задают на собеседованиях в гугл и амазон - у нас их добавляют в ЕГЭ по информатике))

[@xender2112]

Иначе некому в гугле будет работать. Вы же не думаете, что таланты из Стэнфорда пойдут в Гугл работать? Такие идут работать в более важные стратегические структуры.

[@user-bh3mm6ck4q]

А не проще по нижней и правой границе поставить 1, а середину считать слева направо, складывая низ и лево, и без рекурсии, и вроде все отлично будет работать, а ещё проще посчитать число сочетаний, но, как я понял, задача не под это заточена

[@user-dx9yq5js2c]

Хорошо объясняешь. Но почему так мало видео?

[@DaemonHK666]

Пашет человек на гугл/амазон/фейсбук, некогда

[@grbak]

Пушка

[@viktorstupetskiy1926]

Отупление в степени бесконечность!!

[@piktogor]

Прикольно) спасибо за видео

[@n4trojan]

А как поможет переданный через параметры массив arr? При вызове helper(n, m-1, arr) в Arr заведомо небудет данных о n, m-1, так как при таком подходе данные передаются только по рекурсии ВНИЗ.

[@user-bo7yz7wb1h]

Массивы в java передаются по ссылке. То есть от начала до конца выполнения будет существовать один общий массив

[@n4trojan]

@@user-bo7yz7wb1h Спасибо. Это - все объясняет.

[@a98cb985]

Спасибо большое, с 3го раза допер

[@GGamess]

похоже надо второй раз посмотреть, а потом еще раз)

[@ojer101]

А почему ответ на задачу из гугла 3 , а не 4 ?

[@ojer101]

Понял,прослушал, что он в низ не может ходить.

[@alexkuznetsov9008]

эту задачу можно решить гораздо проще и красивее, без циклов, условий и прочего. можно составить формулу числа возможных путей от N и M ) вот как это можно сделать: с каждым ходом робот продвигается либо вверх либо вправо, следовательно все маршруты имеют одинаковую длину и отличаются только последовательностью ходов вверх и вправо, количество ходов вверх = N-1 количество ходов вправо = M-1. наша задача - найти, сколько есть вариантов расставить N "вещей" в (N+M-2) позициях ("вещи" не уникальны). для этого есть формула в комбинаторике. помогите мне её вспомнить))))

[@user-iq9ll8lz9m]

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

[@taylerdivers3870]

Фильм "Куб" вспоминается. Разница в том, что в случае ошибки в гугл тебя не убьют)