Задача из Собеседования в Google на Динамическое Программирование: Количество Уникальных Путей
HTML-код
- Опубликовано: 6 июн 2020
- Классический пример применения динамического программирования для ускорения работы рекурсивной функции.
Различные вариации этой задачи часто спрашивают на собеседовании в Google, Amazon и Facebook.
Эта задача на LeetCode: leetcode.com/problems/unique-...
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
Это простая задача, вот у нас на заводе, начальник цеха ставит задачу
- Сделать дох3я из них3я и еще премии лишает если не выйдет. О как!
Cрочно пришлите нам его телефон! (Директор Гугля)
Когда начальник требует "дох3я из них3я" очень важно убедить что "нах3й нужно" и таки получить премию! Вам просто не хватает навыков убеждения! :-D
Я в таких случаях начальнику всегда напоминаю один анекдот:
Василий Иванович и Петька терпят крушение, и тут начинается диалог:
-Петька приборы?
- Двести
- Что двести?
- А что приборы?
Так что умейте добиваться информации от кого либо.... в том числе и постановки задач по SMART.
Можно начать с заказа сырья у поставщика: дох3я килограммов самого чистого них3я. Можно даже сказать, что поставщик готов подождать с оплатой суммы в дох3я рублей, пока кладовщик примет заказ. Думаю на этом всё и закончится.
@@user-ug4jp7ck2x А потом сказать что поставщик оказался липовый, или банкротство объявил, в результате чего мы получим то самое нихЗя и как следствие дохЗя проблем. Задание выполнено))
мне кажется что проще подойти к задаче с точки зрения вероятностей, любой путь будет содержать (n -1) шагов направо и (m-1) шагов вверх, тогда надо просто посчитать количество их возможных комбинаций, для n=5 и m=4, тогда решением будет (4 + 3)!/(4!*3!) = 35 вариантов. сложность такого алгоритма O(1).
Пояснения: (4 + 3)! это количество возможных уникальных вариантов если каждый шаг уникален, но у нас есть есть однотипные неуникальные серии шагов которые сокращают это количество, 4 одинаковых шага сокращают количество комбинаций в 4! раза, и другие 3 одинаковых шага сокращают в 3! раза.
Вы написали мои мысли :)
быть может с точки зрения комбинаторики?
@@Maksim_C ну да скорее комбинаторика, есл угодно
Все так, только сложность условно константная, все-таки, т.к. факториал не считается за константу, если нет заранее просчитанной таблицы готовых значений. А так получается О(n+m).
это всё хорошо в самом простом идеальном случае, который описан в видео. давайте выберем несколько клеток посреди поля и запретим через них ходить. или добавим условия, что из некоторых клеток можно ходить только вверх, а из некоторых - только вправо. или добавим веса при прохождении через клетки. алгоритм, описанный в видео, продолжит работать, с минимальными доработками.
Александр, прекрасно объясняете, спасибо!
Тот случай, когда только начал учиться программированию и понимаешь, что скоро обучение закончится
Ну че там, как дела?
@@user-vu6hn4ul2i, видимо закончил
Выучи язык, а эти задачи можно только запоминать и выписывать. Подход, сейчас решу сам за часок из головы, тут только сломает тебя. Просто найди готовое решение , пойми его, запомни
и иди на новую задачу.
@@axiswait5339можешь подробнее расписать свою точку зрения?
🤣 Мужик, я не знаю учишь до сих пор программирование или нет, но с юмором у тебя однозначно все в полном порядке 😅
Александр. Спасибо. Наткнулся случайно. Прекрасный материал и его подача. Не останавливайтесь!
Спасибо, полезно. Мне очень помогает знать простую идею, стоящую за алгоритмом. Потом очень легко распространить её на более сложные варианты.
Завтра на всех галерах страны за 200$ в месяц будут спрашивать о Динамическом Программировании. Мне особенно нравится, когда сидит "Байкер" часный предпрениматель и спрашивает "Что вы знаете о культуре нашей компании". Автору спасибо за видео.
@DaXz на самом деле видел тех кто пол года бесплатно работал, ради того чтоб начать и получить хоть какоето резюме.
@DaXz стажеры каторые работают 8 часов в сутки. Нет это джуны. Там были реальные работы и реальные требования.
@Руслан Грищук пол украины так работает, от дизайнеров до фулстакеров. Я рад что вы в розовой зоне и у вас все хорошо.
@Руслан Грищук Могу сказать тоже про наши компании - только лох не нанимает скиловых людей за копейки а ищут нинзь и фей, а потом собирают команду сказочных дол№оебов и такие - раньше мы брали с опытом 7 лет надо повысить планку хотябы в трое. А потом ХРМ пишет тебе нам нужен чел с опытом Вью не менее 20 лет - браво!
@@AWoh51EIbvd половина компаній України, які працюють на ринок України. Але у нас 90% айті - це аутсорс, або стабільні продуктові компанії.
Очень круто объясняешь! Посмотрел не отрываясь, спасибо!!!
Стоит еще упомянуть, что в первом случае затраты памяти - O(1), а вот во 2 случае - O(n*m) (в конце алгоритма у нас в памяти будет вся матрица), и это в обоих случаях без учета затрат памяти на рекурсивные вызовы. Притом, можно улучшить затраты памяти до n:
1) Пишем итеративный цикл с проходом по строкам слева направо.
2) Не трудно заметить, что для вычисления очередной клетки, весь массив нам не нужен, а нужна только предыдущая строка, которую мы вычисляем на предыдущем шаге итерации, и клетка слева, которая также уже вычислена.
В первом случае сложность для памяти не O(1), каждый вызов ф-ии это новый элемент в памяти
@@user-fo6dm5gy8e внимательно читаем сообщение еще раз и что мы видим??? "это в обоих случаях без учета затрат памяти на рекурсивные вызовы"
@@alexeys1789после чего на собеседовании идём лесом, ибо затраты на рекурсию тоже всегда надо учитывать, иначе это ошибка. Стек растет пропорционально глубине рекурсии
@@volervagashim ахахахах, если это рофл, то харош))0
@@alexeys1789 поясни, плз, видимо я не понимаю чего-то
Саша, здравствуйте! А вы будете продолжать вести канал? Сейчас очень актуальны ваши ролики с задачами и теорией (если она планируется), все очень доходчиво и понятно, спасибо!
очень доходчивое и наглядное объяснение, спасибо! с меня подписка! (пришел с гугл рекламы). Так же стоило упомянуть комбинаторное решение. Нужно будет посчитать количество перестановок вверх (их m-1, если m - высота поля), и вправо (аналогично n-1).
Спасибо! Действительно, так можно и это очень красивое решение. Но решил не перегружать это видео.
@@sashalukin очень зря, это наиболее простое и красивые решение)
@@sashalukin, не перегружать видео и поэтому там 8 мин абстракных размышлени, не самый очевидный алгорим, и избыточная реализация решения.. На работу звяли?
@@sashalukin а ответ в большой таблице равен 35?
Нашёл его же, загнал в код.
Получил не ожидаемую мной особенность: при больших значениях m и n факториалы легко вылетают даже за границы лонг инта, т.е. требуется правильно выделять память. А вот метод с вспомогательной таблицей менее требователен в этом конкретном аспекте.
P.S. А проще и элегантнее всего задача кодится заполнением аналогичного массива из исходного угла в конченый. Можно заполнять "полосками". В первой колонке все единички, в первой полоске тоже единички, а в каждой клетке потом - сумма соседей снизу и слева. Так полоска за полоской и заполняем. И кодить просто (рекурсии-то нет), и цифирки не большие. И особенно пикантно то, что если вычисления большие и их надо "на паузу" ставить, то запоминать надо самый минимум: текущее состояние массива и координаты последней заполненной клетки.
Спасибо, за понятное объяснение, лайк!
Отличный ролик!
6:55 мемоизация , спасибо )
Спасибо, интересный разбор.
Можно комбинаторикой: пусть a - количество ходов вверх ИЛИ вправо (неважно), b - общее количество ходов. Тогда ответ на задачу равен C из b по a
Воот! Думал ровно про то же самое. Тут хватит одной формулы без циклов.
Звучит логично, но не совсем понятно)
А тк надо посчитать побыстрее, то воспользуемся асимптотикой сочетаний через экспоненту - это и будет примерный ответ, который можно посчитать аж за lon (n + m))
Сначала посчитал рекурсией (правда, немного другой), потом подумал - а почему нельзя аналитически решить?
Получил тот же ответ, что и вы: Выборка из (m+n-2) по (m-1). Или, что то же самое, выборка из (m+n-2) по (n-1).
Или, ответ = (m+n-2)!/{(m-1)!*(n-1)!}
Видео как бы "обосновывает" применение сильных сторон компьютера, а вы поднимаете вопрос силы человеческого мозга.
Ну да, если кончится бензин кругом - те кто быстрее и дольше могут бегать будут в выигрыше, но как правило человек (и даже дедуля и даже ребёнок) используя машину становится сразу быстрее бегуна, причём (и это самое главное!) НЕ заморачиваясь на проблеме, а решая задачу.
Это видео ценно как раз тем, что показано как использовать силу (преимущество) компьютера, который может и не оптимально (как человек оптимально - аналитически) решит задачу, но целый _класс_ задач зато где надо "быстро смоделировать" (рекурсией - тут силён комп конечно) не заморачиваясь.
спасибо за разьяснение
спасибо за видео, очень помогло!
Ох, ребята. Снимаю шляпу перед вами! Эта область для меня темный лес. Всегда вами восхищался!
Я не смог досмотреть это видео, просто потому, что у меня начались "вьетнамские флэшбэки" с сотен собеседований, где задавали крайне полезные и актуальные вопросы, которые я точно должен уметь решать.
"Где Вы видите себя через 5 лет?" да в вашем офисе буду бумажки перебирать, где ж ещё?!
Я ща на старости флешбеки как фильмы смотрю, сьэкономил на кинотеатрах и купил клей момент и ласты, перед сном надеваю на всякий случай и наслаждаюсь 5Д без искуственного интелекта, последних технологий, промисов и блокчейнов. Замомните - То что нас не убивает, н№XeRa не делает нас сильнее, просто убивает потом.
Как уже упомянуло несколько людей в комментариях задача действительно может решаться просто по формуле, но если использовать рекурсию как в видео, то более простым вариантом пожалуй будет это:
int paths(int n, int m) {
if(n == 1 || m ==1)
return 1;
return paths(n-1,m) + paths(n, m-1);
}
Если точка находится на одной линии с роботом, то очевидно только один путь к ней, поэтому возвращает единицу, таким образом выход за рамки поля невозможен, и считать его не надо, такая рекурсия как по мне выглядит намного проще, да и для прямого пути в 5 клеток не надо будет вызывать 5 функций пока они не дойдут до робота, а сразу возвращает единицу.
реально интересная задача!
Спасибо большое! Стопнул на 1:02 и решил самостоятельно, после чего сверился. Советую всем так делать, хотя бы устно, в уме.
Можно, кстати, оптимизировать использование ОЗУ чуть меньше, чем в 2 раза. Это задача на внимательность, на нахождение треугольника паскаля в ней. А прелестное свойство треугольника паскаля - его симметричность, нам достаточно хранить его половину вместе с главной диагональю (для реализации подсказка: arr[n][m] считается как обычно, arr[n-1][m]+arr[n][m-1], а главная диагональ - arr[n][n] = arr[n][n-1] * 2).
Динамическое программирование - это не только запоминание промежуточных результатов, но также и само рекурсивное решение. Также как при вычислении числа Фибоначчи, данную задачу можно решить как простым циклом, так и рекурсивно. И именно рекурсивное решение с запоминанием промежуточных результатов является динамическим программированием для обоих задач.
Есть видео, (Тимофей Хирьянов "Динамическое программирование сверху и снизу"). Смотрел его через пару дней после этого видео.
Обычно можно переделать рекурсию на цикл и это улучшает производительность.
Для обЕих задач
Если я не ошибаюсь, то можно без рекурсии намного проще. Нужно в каждой клетке (i,j) просчитать к-во вариантов. Начинаем с нижнего ряда слева направо - все единицы (т.к. снизу клеток нет, а слева все время 1). Начитая со второго ряда снизу значение К(i,j) = значение клетки слева К(i-1, j) (для клетки К(1,j) будет 1) + K(i,j-1). И так, пока не дойдем до точки К(n,m)
Да, можно прежде и левый столбец заполнить единицами. Однако это не динамическое программирование.
Плюсую
Для первой задачи ответ 4, но это так, придирка. Видос отличный!
4 - это если он вниз ходить умеет
@@rizhiy87, вы правы, я упустил исходные требования, да, три варианта.
Хороший ролик, хорошее объяснение. Мы задачи подобного рода аналитически решали на уроках информатики в 6-7 классах (не спец школа), на Basic. Сижу и думаю, то ли учитель хороший был, то ли что-то в мире поменялось. :)
Сейчас аналогичная задача даётся в ЕГЭ, причём это не самая сложная
хз как я сюда попал, но в принципе не обязательно уходить за границы матрицы - можно упростить дно рекурсии `if (n == 1 || m == 1) return 1;`
а если n уже равно 1, а m ещё нет? У нас же остаются еще куча вариантов развития событий
@@evgeniibubolev9881 нет, не остаются - возможен только один путь по прямой вдоль "стеночки"
@@firejvlz ох, спасибо, вы конечно правы
спасибо!
изначально не понимал с какой стороны подойти к решению)
В итоге пришел к решению с комбинаторикой.
Но решение автора мне очень понравилось. Правда что рекурсия уже не подойдет на очень больших m и n
Можешь написать как это комбинаторикой решить?
Спасибо. Окончательно убедился что да ну его нафиг.
Путь однозначно задается как n - 1 стрелка вправо и m - 1 стрелка вверх, выпишем стрелки в ряд в произвольном порядке (всего в ряду n + m - 2 стрелок). Тогда число способов расставить здесь n - 1 стрелку вправо равно количеству сочетаний из n + m - 2 по n - 1 (или по m - 1, что тоже самое). Ответ: (n+m-2)! / (m - 1)! / (n-1)!
интересная задачка, своеобразное комбо матрицы и дерева)
Почему у тебя так мало подписчиков я считаю то-что ты хороший блогер жилаю удачи и дальше
Спасибо!
Знаешь иногда я завидую таким как вы Веть у меня нет даже канала не то что подписчиков а ты можешь помочь нам
@@user-td5rb5wd1m Ютуб - это развлекаловка, людям нужны котики и похабные анекдотики, никто не будет после работы динамическое программирование смотреть.
@@zelmanfeig5404 и что?
@@zelmanfeig5404 Я просто выразил свои мысли
Это жестко конечно
Прикольно) спасибо за видео
А вот и спасибо)
Это ж простейшая комбинаторика :)
И че я сюда зашел? Почуствовал себя тупым и пошел дальше 🤓
вспомнил basic и fortran 4
и пошел дальше играть в видеоигры? )))
@@ovsyannikovo а чего добился ты 😅, я вот много игр прошел - дибильных
@@GrAlUnrealEngine ну для начала я смог завязать с играми 🙂
@@ovsyannikovo жаль тебя 😂 (рофлю), а меня в их разработку затянуло.
Контент супер!
_Динамическое программирование_ - способ решения сложных задач путём разбиения их на более простые подзадачи.
Вся наша жизнь немножно динамическое программирование :-)
Видео как бы намекает зачем компьютеру надо столько много памяти (на стек вызовов рекурсии, на массив для мемоизации) :-)
Тут много людей пишет в комментариях, что можно решить оптимальнее и аналитически вообще (сведя к формуле), но если хорошенько подумать, то показана то не конкретная задача, а _класс_ задач.
Ну и опять же, компьютер изобрели чтобы НЕ заморачиваться. Да, можно интеграл красиво аналитически посчитать, а можно методом трапеций численно.
Аналитически это конечно же красиво и "интеллектуально элитно", но в суровой реальной жизни когда заказчику надо "вчера!" и результат нужен "прям щас и один раз!" и "уже всё!" и у директора дёргается от этого глаз от нервов всех этих - математика-аналитика-теоретика раньше уволят нафиг (и заводу может кирдык придёт), ну или премию дадут "Петровичу" который методом трапеций за 5 минут прикинул и сказал "ах**но! материала хватит! вот смета!" :-))))
Разве математик-теоретик не посчитает интеграл по красоте сейчас 5минут?
@@akiiaev математик-теоретик - товар штучный, а решения надо принимать много где, и тут на помощь придёт "числодробилка" которая сделает даже дурачка "великим математиком" ;-)
в мире много рукожопов - поэтому изобрели санчала трафареты, а потом и ЧПУ станки, в мире много тугодумов - поэтому изобрели компы и численные методы и методы мат.моделирования. и это дало возможность даже дурачкам кормиться и размножаться, алилуйя! :-D
но конечно же "для любителей помучаться" (мазохистов) остались ручные дрели, лобзики, логарифмические линейки, кульманы для чертежей вручную и прочие "орудия пыток" :-D
но мне как-то нравится в 3D принтер или ЧПУ загружать чертёж, который я могу поправить в САПР если что не переделывая полностью. видимо я не дошёл до "дзена", мне результат как-то важнее процесса.
Примерно в этом и заключается талант грамотного технического менеджера: отличать задачи, которые нужно решать быстро и в лоб, от тех, которые нужно решать долго и красиво. И в промышленной разработке, конечно, первых гораздо больше, но всё же не 100 %.
Добрый день. Можно ли решить задачу следующим способом? Робот может двигаться только вправо и вверх, т.е. каждая клетка из которой можно двинуться вправо или вверх является развилкой и дает +1 путь - это не крайние правые и не крайние верхние клетки. При поле размером 1 клетка в ширину или 1 клетка в высоту у робота только один путь. Т.о. получаем алгоритм: h=5; n=4; ways_count=1; hi=1; ni=1; for(hi=1;hi++;hi
Развилка даёт не +1 путь, а +к путей , где к - количество путей до этой клетки.
Проверьте сами себя: посчитайте для квадрата 4*5 "руками" (должно получиться 35) и своим алгоритмом
Можно решить задачу представив клетки в виде бинома Ньютона
Саша , отлично объясняешь! Хоть я и вообще не хочу быть программистом )) Я пилот, но умение рассказывать у вас однозначно есть!
Ну так, пілоти то раза 2 більше, в середньому, отримують)
@@denisdragomirik не в деньгах счастье
@@pilotjenya тоді давай до нас ;)
@@denisdragomirik нi. Спасибо :)) мэнi и тут дуже гарно
@@pilotjenya 😁😁
2001 год. У нас тогда появился компьютерный класс в школе и на информатике мы писали программу с похожим решением. Только там был не робот, а кенгуру.
Если кенгуру - тогда m-n заменяем на k-z . Только так и не как иначе!
@@maksimr3175 а для черепашки x-y
@@A1bertG шуточки шутим?! Какие "ХУ"? Ну какие ху? Какие ху. Это элементарно ! Если черепашка значит n-z !
Шучу. Всех благ! Кидаю краба. Присел на корточки. Семечки плюю в кулёчек .
Можно увидеть в этом треугольник Паскаля.
Номер ряда L = n + m - 2.
Искомый член ряда P = Min(m, n) - 1
Результат L! / (P! * (L - P)!), то есть число сочетаний из элементов по Ну и всё, не нужно так заморачиваться.
Дабы не мучить компьютер лишний раз, число сочетаний высчитываем как "Произведение P последних из L делить на P!"
И тогда сложность из O(m+n) становится O(min(n, m)).
Как бы сделать ещё красивее?
поле размером 2000 х 2000, с факториалом не мучать компьютер лишний раз не получится
@@user-iq9ll8lz9m Для компа перемножить тысячи чисел - десятая доля секунды. Надо, конечно, позаботиться об избежании переполнения, но всё равно это будет гораздо быстрее в сравнении с оббеганием 4 000 000 ячеек.
К тому же у нас не растёт потребление по памяти, чего не скажешь про код автора.
@@YevhenDiulin так а астмптотику подсчёта факториала вы знаете?
Плюс следить за переполнением легко, но что делать если оно будет?(а оно будет)
Длинная арифметика или варианты получше?)
Все это красиво только на листочке, а на практике чёт не очень
@@freedomtv2295 Можно взять тип с плавающей точкой и не считать факториалы отдельно, а сразу считать число сочетаний: умножил на один член чеслителя, разделил на один член знаменателя, потом на другой член чеслителя и на другой член знаменателя. Есть пути в обход.
@@YevhenDiulin идея с поочередным умножением это хорошо, но типы с плавающей точкой сразу нет. Это гора проблем, там от ответа не останется даже и следа
После твоего душевного рассказа на нашем собеседовании, я бы перевернул твой рисунок на 180 градусов, увидел твои округлившиеся глаза и сказал - спасибо, что пришел, пригласи пожалуйста следующего!
Можно еще оптимизировать вдвое, если учесть, что paths(n, m) === paths(m, n)
Решал такую задачу много лет назад на позицию джуна
Если в задании нельзя использавать комбинаторику (хотя этот способ самый лучший) можносделать программу ещё проше,
На языке паскаль:
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]);
Да уж, уже подзабыл программирование со школьных лет не занимался
Половина комментаторов пропустили важную часть условия и умничают. Всё, что нужно знать о комментаторах
Обход шахматной доски конем куда сложнее рекурсия. Автору респект.
Это на самом деле задача из комбинаторики для 7-8 класса. Здесь можно даже увидеть треугольник Паскаля, который разворачивается направо-вверх:
...
1 ...
1 4 ...
1 3 6 ...
1 2 3 4 ...
1 1 1 1 1 ...
Число в каждой клетке равно количеству маршрутов, ведущих в неё из начальной клетки.
Ну и одновременно с этим, числа, из которых состоит треугольник Паскаля представляют собой кол-во сочетаний, поэтому ответ C из n по m.
Фишка в том что посчитать биномиальный коэффициент всё равно не просто, а если на машине умножение долгая операция то и без дополнительной памяти не обойтись
Рекурсия почти всегда красивое решение. Хотя и трудно для понимания иногда. Да и цена алгоритма очень высока.
Если у нас задача просто посчитать пути, тогда предлагаю такой вариант:
Если ручкой провести все пути, то можно заметить следующее- есть 2 экстремальных пути, когда робот пойдет по периметру, а также пути внутри периметра. Если посмотреть на все пути, то в поле справа от каждого остается на один квадрат больше, и фигура, образуемая этими квадратами будет расти равномерно, как выпуклая геометрическая фигура.
Говоря проще, количество путей будет равно сумме (m*n) - (m+n-1) +1,
где (m*n) -это количество всех квадратов, (m+n-1) - это сумма квадратов в случае, если робот пошел экстремально вверх до конца и направо до конца, а +1 - это путь, который он прошел экстремально вправо до конца, а потом вверх до конца
Но данное условие не подойдет в случае, если имзенится поведение робота. Надеюсь хоть чтото понятно, если будет интересно - приложу рисунок
Почему цена алгоритма высока? Рекурсию необязательно реализовывать через вызов той же функции. В этой конкретной задачи решается массивом 2*M или 2*N.
@@airn587 да гдето читал, что рекурсивные функции норм так жрут
А как делать не через функцию? через цикл с ветвлением?
Для m = 3, n = 3 проверь. По твоей формуле 5, по факту 6
@@airn587 ну и недавно посмотрел про рекурсии. Если они довольно большие - просто ловишь stackOverflow
@@user-bh3mm6ck4q блин) я уже не помню че там было))
Ну в целом я к тому, что не всегда нужно решать задачу, чтобы она решала любые вариации впоследующем. Если есть возможность сделать тупо и просто, потратив меньше часов и энергии, то, возможно, это лучшее решение.
А если вдруг потом понадобится расширение - тогда уже подумать над алгоритмом. Опять же, зависит от котекста
У меня только один вопрос: зачем решать перебором то, что считается аналитически?
Роботу нужно сделать n движений вверх и m движений вправо. Вполне очевидно, что количество путей равно числу сочетаний из n+m по n.
Можно свести задачу к графу, построить матрицу смежности и возвести в степень k, где k - расстояние между вершинами. Это будет где-то (m*n)^2.5 сложность, зато потенциально найдет решение в общем лучае. + Будет задел на применение прочих графовских алгоритмов
Можно решить задачу через комбинаторику и найти ответ в одну строчку вычислений)
@@alexanderpalagin4662на больших m и n устанешь, эти факториалы не влезут в размер переменной, нужно будет с бубнами плясать, лучше загрузить процессор и точно знать, что оно выполнится, а не упадёт, потому что комп не сможет оперировать в формуле факториалом от миллиарда)
чётко
Как не программист сломал себе мозг пока додумался почему массив на единицу больше
Эту задачу можно решить ещё быстрее увидев, что это треугольник паскаля, правда надо ещё знать формулу его. Тогда апроксимация времени работы алгоритма будет = О(n+m).
Эту задачу можно решить и за константное время,, используя формулу количества сочетаний. Только для конкретно этого варианта задачи нужно уменьшить и ширину, и высоту сетки на 1.
@@user-es7jg3qi8j Для количества сочетаний придётся считать факториалы, каждый из них считается за время O(n). Тогда для этой задачи О(max(n,m)).
@@user-dp6th8fx4w Там факториал от n+m
@@kikislav Вы написали, и я задумался. Раз уж так, можем считать факториал с конца, то есть a*(a-1)*(a-2)*...*(a-i), где а=n+m в нашем случае, а i=min(n,m); попутно же будем считать количество перестановок (i факториал); поделим одно на другое и получим искомое количество сочетаний. Выходит что сложность алгоритма и того меньше - О(min(n,m)).
@@user-dp6th8fx4w На самом деле апроксимация вычисляется более сложным путём, так-как апроксимация умножение двух чисел длиной n и m равна O(max(m, n)) Вы можете сами проверить, написав программу, потому что компьютер умножает числа примерно как мы, в столбик.
Все проще. Это треугольник паскаля.
Время работы О(2*(m + n))
В случае если n>=2 и m >=2 ответ записывается формулой
(n + m - 2)!/((m - 1)! * (n - 1)!) //просто найти факториалы отдельно и посчитать
Иначе ответ 1
Вроде все понятно и просто ,но если самостоятельно сделать ,я бы прикурил )
А вариант "змейкой" не учитывается? Или нужен кратчайший путь?
0:25 . Робот не может ходить вниз, то есть вариант змейки не возможен в принципе
@@surekt4780 , да, я уже понял, просто не внимательно послушал условия.
Уважаемый автор, на 5.52 сек клетка 31, говорит что там количество ходов 1 шт. А как же последовательность 11 - 12 - 22 - 21 - 31 ? Может условие чуть иное в задаче? получается что мах количество ходов для n=3 m=2 равно не 3 а 4. Спасибо
Кудой, кудою? По ТЗ робот может ходить лишь вправо и вверх.
Спасибо за мемоизацию
Спасибо большое, с 3го раза допер
похоже надо второй раз посмотреть, а потом еще раз)
Для относительно небольших размеров грида самым быстрым решением будет формула биномиальных коэффициентов, так по использованию памяти мы получим O(1)
там формула еще проще
@Mike я не считал максимальный грид для моего решения, но для решения на литкоде мне хватило трёх переменных long long и небольшой оптимизации. В итоге самый быстрый результат на сайте.
Разве формула биноминальных коэффициентов даёт О(1).
Там же, кажется, О(n)
@@avshukan ты не совсем прав, фактически нам нужна петля для подсчёта факториала, но при минимальном упрощении мы считаем только то колличество итераций, которое будет меньше (k!-1 Или (n-k)! -1)
@@adventurer_v
ну, то есть O( min(k, n-k) )
в худшем случае, это О(n/2)
так?
вот легче решение для понимания. Если идем вправо на одну клетку тогда это приравниваем к 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 для первой итд
У нас эта и подобные ей задачи были в 8 классе на уроках информатики. В Паскале писали всякие алгоритмы для роботов.
Всегда ненавидел это дело. По сути, весь 8й и 9й класс были посвящены тому, чтобы робот бегал по карте с препятствиями и искал выход наиболее оптимальным образом. Вечно ошибался и либо написанная прога не работала, либо робот шёл не туда, куда надо, либо шел куда надо, но не оптимальным способом, либо учителю не нравился сам код...
В общем, с программированием не сложилось :)
у нас была "черепашка" и "робот-пылесос". робот нужно было программировать на русском. это был 6й класс и я обожал это дело, тогда и влюбился в программирование окончательно :)
А у нас вообще не было компьютеров.
Интересно кто это применил это на практике больше одного раза?
Можно обратить внимание, что это просто повернутый треугольник паскаля и решить задачу просто фомулой C из n по k, нет? Или я чего-то не догоняю?
с чего-то вдруг было принято, что если квадрат 1 на 1, то у робота 1 путь, хотя на самом деле пути нет, а не он пустой, т.к. робот никуда не движется. Дальше можно не смотреть, как уже написали в комментах, задача решается гораздо проще исходя из логики и без рекурсии
Пока такие задачи задают на собеседованиях в гугл и амазон - у нас их добавляют в ЕГЭ по информатике))
Иначе некому в гугле будет работать. Вы же не думаете, что таланты из Стэнфорда пойдут в Гугл работать? Такие идут работать в более важные стратегические структуры.
Всегда думал, что динамическое программирование это нечто крутое. А оказывается это просто кэш данных?
Добрый день! Возможно, я чего-то не понимаю, но я вижу здесь классическую рекурсию. Да, есть двумерный массив состояний, но заполняется он в рекурсивной функции. Вся прелесть ДП, на мой взгляд, как раз в том, что рекуррентное соотношение обрабатывается в цикле без применения рекурсии.Я могу предложить свой вариант. Если я неправ, то прошу дать разъяснения.
Добрый день. Опишите пожалуйста свой вариант с заполнением массивов. Я учусь и интересно как это относительно данной задачи
матрица 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
Хороший контент, жаль что Саша канал забросил.
Вообще не понял, как прийти к выводу что: paths(n, m) = paths(n - 1, m) + paths(n, m - 1)
мне кажется это потому что мы считаем число путей (комбинаций как прийти) к точке А и к точке В. Которые находятся либо слева либо снизу.
Это просто разложение первого хода. Ты можешь пойти вверх и тогда высота оставшегося поля уменьшится на 1. Или ты можешь пойти вправо и тогда ширина поля уменьшиться на 1. Соответственно общее кол-во путей - это просто сумма путей для обоих вариантов.
хм, почему путь 21 22 12 13 до двери не рассматривается? Почему учитывается только самый короткий путь?
Пробовал данное решение использовать на leetcode, получил перерасход времени. Вот более быстрое решение на JS:
var uniquePaths = function(m, n) {
let row = new Array(m).fill(1);
for (let i = n -2 ; i>=0; i--)
{
const newRow = new Array(m).fill(1);
for (let i =m-2; i>=0;i--){
newRow[i] = newRow[i+1]+row[i]
}
row = newRow;
}
return row[0]
};
Хорошее решение, только для чего используешь два массива? да и проверку всё же лучше делать, чтобы код ошибок не выдавал ;)
function uniquePaths(m, n) {
if (m < 1 || n < 1 || (m === 1 && n === 1)) return 0; //считаю, что поле [1;1] также не имеет решения
if (m === 1 || n === 1) return 1;
let arr = new Array(m).fill(1);
for (let i = n - 2 ; i >= 0; i--){
for (let j = m - 2; j >= 0; j--){ //для лучше читаемости кода лучше всё же переменные называть по разному
arr[j] = arr[j+1]+arr[j]
}
}
return arr[0]
};
Только функция 2^(m*n) - показательная, а не экспонента.
Спасибо за видео!
А не проще по нижней и правой границе поставить 1, а середину считать слева направо, складывая низ и лево, и без рекурсии, и вроде все отлично будет работать, а ещё проще посчитать число сочетаний, но, как я понял, задача не под это заточена
по моему задача решается легче математически. всего шагов n+m-2 и надо выбрать лишь номер шагов вверх или вправо, тоесть ответ С из n-1 по n+m-2 или C из m-1 по n+m-2 тут как удобнее, т.к. числа эти будут равны
самое главное в подобных задачах - уметь применять знания полученные при решении. а то приходят литкодовцы и кроме алго и систем дизайн интервью ничего пройти не могут. да и на практике говнокод лютейший генерируют. идея которая была заложена в алго интервью уже изжила себя и это абузят все кому не лень.
А сколько даётся времени на её решение?
Думаю лучше было бы использовать вместо робота монстра из корпорации монстров😄
А как поможет переданный через параметры массив arr? При вызове helper(n, m-1, arr) в Arr заведомо небудет данных о n, m-1, так как при таком подходе данные передаются только по рекурсии ВНИЗ.
Массивы в java передаются по ссылке. То есть от начала до конца выполнения будет существовать один общий массив
@@user-bo7yz7wb1h Спасибо. Это - все объясняет.
Спасибо. Решение очень красивое и простое, но если вы ищите путь, то где препятствия? Если есть препятствия, то путь будет с шагами назад и вниз, а это может привести к циклам, которые можно исключить если на карте ставить метки, где идёт текущий прогон. Вы передаёте в рекурсивной функции параметр - таблицу, то есть таблица должна остаться в стеке при каждом вызове, но это при росте размера карты приведёт к ошибке Stack Overflow? Избежать ошибки можно если сделать "прямое" решение с поиском путей от первой точки, заменив рекурсию на цикл, а таблицу из параметров сделать переменной.
Решение автора ролика не самое простое и далеко не самое красивое! ;)
И ещё вы не внимательно слушали условие задачи - робот может ходить вверх или вправо, но он НЕ МОЖЕТ ходить вниз или влево!
@@ukrainekiev3990, вы серьёзно?
Просто привычки программиста, ТЗ меняется на ХЗ в любой момент.
В общем, можете рассказать пользователям чего робот "НЕ МОЖЕТ".
@@Aimilomim, при чём здесь "можете рассказать пользователям"? Речь идёт о том, что вы НЕВНИМАТЕЛЬНЫЙ и невнимательно слушали условие задачи! Невнимательность это не привычка программиста, это привычка раздолбая, от сюда ваши кривые коды со всеми вытекающими ))
@@ukrainekiev3990, в хорошей программе должна быть возможность модификации. А у пользователей всегда есть новые требования.
Вы считаете, что рекурсия лучше циклов? Параметры рекурсии не имеют значения?
@@Aimilomim забей. Он не поймёт
Хорошо объясняешь. Но почему так мало видео?
Пашет человек на гугл/амазон/фейсбук, некогда
Разве функция хелпер типа может вернуть массив инт?
1) а. С массивом будет вызываться функция повторно для тех клеток, которые равны нулю; б. Массив должен быть заранее известного размера либо динамически перераспределяться - будет развесистый спагетти-код. Поэтому надо функцию вызывать из экземпляра класса, добавить поле с мапой и в начале функции ифчик с проверкой на присутствие в мапе, а в конце добавить вхождение в мапу. 2) a. рекурсия сама по себе ограничивает глубину вызова и стоит это как-то учесть, например, выбрасывать исключение при слишком больших (m, n); б. Ддя больших значений m и n, которые не позволят массиву/мапе поместиться в кэш процессора, будет производится вычитка из памяти. Операция эта долгая, и прежде чем добавлять такую реализацию, стоит проверить на бенчмарках выигрыш от нее - вполне возможно, что повторное вычисление будет быстрее
По сути массив вы используете как мапу, где индекс == ключу элемента. Согласен, для оптимизации это хорошо иногда работает, массив очень полезная штука, но тут и мапа будет хорошо работать, а читаемость существенно вырастет, поэтому она и должна быть в коде как минимум до того момента, пока на бенчмарках не будет доказана эффективность замены
@@hro688 обычно мапа на порядки медленнее массива...
@@user-uvk в цифрах О большого и то, и то О(1). Понятно, что будут накладные расходы на высчитывание хэша и сравнение объектов, а также на плохо распределяемые объекты, но и в таком случае, например, в джаве, все под капотом достаточно хорошо оптимизируется до O(log N) для сравнимых элементов. И при этом по памяти мы независим от непрерывного участка памяти. В общем, непонятно, откуда взялось "на порядок медленнее", можете пояснить? И в каких компаниях попросили бы писать такой код без мапы (чтобы туда не попасть случайно), если, конечно, там не какую-нибудь встроенную систему реального времени управления атомным реактором внутри него же самого на жестко ограниченном железе пишут
@@hro688 Мапа работает гораздо дольше по следующим причинам: 1) при вставке очередного элемента под него надо выделить память. Это значит, пройтись по спискам свободной памяти, найти там подходящий участок, разделить его на выделяемую и оставляемую в свободной памяти части, организовать необходимые служебные структуры и т.п. 2) из-за наличия служебных полей (от списков памяти) размер выделяемой под элемент памяти больше размера элемента данных. Если элемент данных маленький (как в данной задаче 4 байта), то эти накладные расходы (минимум 2 указателя по 8 байт) в разы больше полезной памяти - это повышает нагрузку на кеш процессора (точнее, снижает вероятность найти данные в нём). 3) при выборке надо посчитать хеш-код, использовать его как индекс в обычном линейном массиве или для поиска по дереву (зависит от реализации мапы) - это требует много машинных команд да ещё с условными переходами (которые имеют свои накладные расходы для процессора), а получение int из простого массива - одна машинная команда. 4) работа с мапой, обычно, это вызовы встроенных функций из библиотеки, а с массивом - прямой код в программе. Это означает лишние обращения к памяти для передачи аргументов подпрограмме через стек, которых нет в работе с массивом.
Мапа имеет огромное преимущество, когда только малая часть возможных ключей (которые могли бы быть индексами в массиве) будет использована. Тут она экономит память, что при больших размерах массива может быть важно. И в случае, когда ключ поиска не может быть напрямую использован как индекс массива, массив отдыхает.
Саша, в итоге устроился куда-нибудь на работу?
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)
Аналогичный алгоритм на питоне
Задача не на ДП, она бьётся формулой. Ясно, что будет сделан m + n -2 ход, из них n - 1 будет вверх. Легко понять, что число маршрутов равно числу способов выбрать из m + n - 2 мест под проход вверх ровно n-1, это сшка из математики. Такую ц-шку можно посчитать за линию (то есть О(m+n)), что быстрее дп, так как дп предполагает сложность O(m*n).
Пушка
А почему массив выделяется m+1 на n+1 а не просто m на n?
Решение за константное время O(1):
(n+m-2)!/((m-1)!(n-1)!)
Случайно, не воспользовалась ли майкрософт данной задачей для отбора программистов для написания windows 10 с критерием - кто решил данную задачу данным способом, берём, а кто другим способом - забраковали. Из чего такая аналогия? Когда комьютеры всё мощнее и мощнее, а работают всё медленнее и менее отзывчиво. По сути: функция О(...) не покрывает всех критериев затрат времени. Ещё есть затраты на вызов стека, дополнительное пространство памяти на хранениние результатов, пустые сравнения и копирование просчитанного значения в память и из памяти. Я вижу лучший путь, чем доп массив. Представленный автором 2й метод несколько быстрее первого, но не отличается принципиально. Спасибо за видео
На 8:12 можно проверять выражение на равенство нулю и возвращать значение из массива ниже
Сэкономим целую строчку😅
Это же обычное задание из егэ по инфе... Когда сдавал это делал за 1 минуту)
Вот + , а говорят, что егэ бесполезно, а оно тут вот как)
Как и многие задачи из собеседований. Штука в том, что если не знаком с задачей или не тренировался заранее решать подобное, то часто можно пойти не тем путём и получить не самое лучшее решение или вылезти за временные рамки.
Вот решение в три строки:
factorial = lambda n: 1 if n == 0 else n * factorial(n-1)
def calculate(m, n):
return factorial(m+n-2) // factorial(m-1)
Я долго думал, что же мне напоминает ДП. Это как кэширование данных, чтобы не приходилось каждый раз обращаться к базе