Задача из Собеседования в Google на Динамическое Программирование: Количество Уникальных Путей
Vložit
- čas přidán 6. 06. 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 поясни, плз, видимо я не понимаю чего-то
Грамотно объяснил, спасибо!
Отличный ролик!
6:55 мемоизация , спасибо )
Спасибо, за понятное объяснение, лайк!
очень доходчивое и наглядное объяснение, спасибо! с меня подписка! (пришел с гугл рекламы). Так же стоило упомянуть комбинаторное решение. Нужно будет посчитать количество перестановок вверх (их m-1, если m - высота поля), и вправо (аналогично n-1).
Спасибо! Действительно, так можно и это очень красивое решение. Но решил не перегружать это видео.
@@sashalukin очень зря, это наиболее простое и красивые решение)
@@sashalukin, не перегружать видео и поэтому там 8 мин абстракных размышлени, не самый очевидный алгорим, и избыточная реализация решения.. На работу звяли?
@@sashalukin а ответ в большой таблице равен 35?
Нашёл его же, загнал в код.
Получил не ожидаемую мной особенность: при больших значениях m и n факториалы легко вылетают даже за границы лонг инта, т.е. требуется правильно выделять память. А вот метод с вспомогательной таблицей менее требователен в этом конкретном аспекте.
P.S. А проще и элегантнее всего задача кодится заполнением аналогичного массива из исходного угла в конченый. Можно заполнять "полосками". В первой колонке все единички, в первой полоске тоже единички, а в каждой клетке потом - сумма соседей снизу и слева. Так полоска за полоской и заполняем. И кодить просто (рекурсии-то нет), и цифирки не большие. И особенно пикантно то, что если вычисления большие и их надо "на паузу" ставить, то запоминать надо самый минимум: текущее состояние массива и координаты последней заполненной клетки.
Саша, здравствуйте! А вы будете продолжать вести канал? Сейчас очень актуальны ваши ролики с задачами и теорией (если она планируется), все очень доходчиво и понятно, спасибо!
Спасибо, интересный разбор.
спасибо за видео, очень помогло!
Можно комбинаторикой: пусть 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)!}
Видео как бы "обосновывает" применение сильных сторон компьютера, а вы поднимаете вопрос силы человеческого мозга.
Ну да, если кончится бензин кругом - те кто быстрее и дольше могут бегать будут в выигрыше, но как правило человек (и даже дедуля и даже ребёнок) используя машину становится сразу быстрее бегуна, причём (и это самое главное!) НЕ заморачиваясь на проблеме, а решая задачу.
Это видео ценно как раз тем, что показано как использовать силу (преимущество) компьютера, который может и не оптимально (как человек оптимально - аналитически) решит задачу, но целый _класс_ задач зато где надо "быстро смоделировать" (рекурсией - тут силён комп конечно) не заморачиваясь.
реально интересная задача!
спасибо за разьяснение
Динамическое программирование - это не только запоминание промежуточных результатов, но также и само рекурсивное решение. Также как при вычислении числа Фибоначчи, данную задачу можно решить как простым циклом, так и рекурсивно. И именно рекурсивное решение с запоминанием промежуточных результатов является динамическим программированием для обоих задач.
Есть видео, (Тимофей Хирьянов "Динамическое программирование сверху и снизу"). Смотрел его через пару дней после этого видео.
Обычно можно переделать рекурсию на цикл и это улучшает производительность.
Для обЕих задач
хз как я сюда попал, но в принципе не обязательно уходить за границы матрицы - можно упростить дно рекурсии `if (n == 1 || m == 1) return 1;`
а если n уже равно 1, а m ещё нет? У нас же остаются еще куча вариантов развития событий
@@evgeniibubolev9881 нет, не остаются - возможен только один путь по прямой вдоль "стеночки"
@@firejvlz ох, спасибо, вы конечно правы
Я не смог досмотреть это видео, просто потому, что у меня начались "вьетнамские флэшбэки" с сотен собеседований, где задавали крайне полезные и актуальные вопросы, которые я точно должен уметь решать.
"Где Вы видите себя через 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)
Да, можно прежде и левый столбец заполнить единицами. Однако это не динамическое программирование.
Плюсую
Ох, ребята. Снимаю шляпу перед вами! Эта область для меня темный лес. Всегда вами восхищался!
спасибо!
Хороший ролик, хорошее объяснение. Мы задачи подобного рода аналитически решали на уроках информатики в 6-7 классах (не спец школа), на Basic. Сижу и думаю, то ли учитель хороший был, то ли что-то в мире поменялось. :)
Сейчас аналогичная задача даётся в ЕГЭ, причём это не самая сложная
Для первой задачи ответ 4, но это так, придирка. Видос отличный!
4 - это если он вниз ходить умеет
@@rizhiy87, вы правы, я упустил исходные требования, да, три варианта.
Спасибо. Окончательно убедился что да ну его нафиг.
Прикольно) спасибо за видео
Путь однозначно задается как n - 1 стрелка вправо и m - 1 стрелка вверх, выпишем стрелки в ряд в произвольном порядке (всего в ряду n + m - 2 стрелок). Тогда число способов расставить здесь n - 1 стрелку вправо равно количеству сочетаний из n + m - 2 по n - 1 (или по m - 1, что тоже самое). Ответ: (n+m-2)! / (m - 1)! / (n-1)!
После твоего душевного рассказа на нашем собеседовании, я бы перевернул твой рисунок на 180 градусов, увидел твои округлившиеся глаза и сказал - спасибо, что пришел, пригласи пожалуйста следующего!
А вот и спасибо)
интересная задачка, своеобразное комбо матрицы и дерева)
И че я сюда зашел? Почуствовал себя тупым и пошел дальше 🤓
вспомнил basic и fortran 4
и пошел дальше играть в видеоигры? )))
@@ovsyannikovo а чего добился ты 😅, я вот много игр прошел - дибильных
@@GrAlUnrealEngine ну для начала я смог завязать с играми 🙂
@@ovsyannikovo жаль тебя 😂 (рофлю), а меня в их разработку затянуло.
Это ж простейшая комбинаторика :)
изначально не понимал с какой стороны подойти к решению)
В итоге пришел к решению с комбинаторикой.
Но решение автора мне очень понравилось. Правда что рекурсия уже не подойдет на очень больших m и n
Можешь написать как это комбинаторикой решить?
Почему у тебя так мало подписчиков я считаю то-что ты хороший блогер жилаю удачи и дальше
Спасибо!
Знаешь иногда я завидую таким как вы Веть у меня нет даже канала не то что подписчиков а ты можешь помочь нам
@@user-td5rb5wd1m Ютуб - это развлекаловка, людям нужны котики и похабные анекдотики, никто не будет после работы динамическое программирование смотреть.
@@zelmanfeig5404 и что?
@@zelmanfeig5404 Я просто выразил свои мысли
Спасибо за мемоизацию
Как не программист сломал себе мозг пока додумался почему массив на единицу больше
Спасибо большое, с 3го раза допер
похоже надо второй раз посмотреть, а потом еще раз)
Рекурсия почти всегда красивое решение. Хотя и трудно для понимания иногда. Да и цена алгоритма очень высока.
Если у нас задача просто посчитать пути, тогда предлагаю такой вариант:
Если ручкой провести все пути, то можно заметить следующее- есть 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).
Эту задачу можно решить и за константное время,, используя формулу количества сочетаний. Только для конкретно этого варианта задачи нужно уменьшить и ширину, и высоту сетки на 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)) Вы можете сами проверить, написав программу, потому что компьютер умножает числа примерно как мы, в столбик.
Можно еще оптимизировать вдвое, если учесть, что paths(n, m) === paths(m, n)
Это на самом деле задача из комбинаторики для 7-8 класса. Здесь можно даже увидеть треугольник Паскаля, который разворачивается направо-вверх:
...
1 ...
1 4 ...
1 3 6 ...
1 2 3 4 ...
1 1 1 1 1 ...
Число в каждой клетке равно количеству маршрутов, ведущих в неё из начальной клетки.
Ну и одновременно с этим, числа, из которых состоит треугольник Паскаля представляют собой кол-во сочетаний, поэтому ответ C из n по m.
Фишка в том что посчитать биномиальный коэффициент всё равно не просто, а если на машине умножение долгая операция то и без дополнительной памяти не обойтись
Можно увидеть в этом треугольник Паскаля.
Номер ряда 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 идея с поочередным умножением это хорошо, но типы с плавающей точкой сразу нет. Это гора проблем, там от ответа не останется даже и следа
У нас эта и подобные ей задачи были в 8 классе на уроках информатики. В Паскале писали всякие алгоритмы для роботов.
Всегда ненавидел это дело. По сути, весь 8й и 9й класс были посвящены тому, чтобы робот бегал по карте с препятствиями и искал выход наиболее оптимальным образом. Вечно ошибался и либо написанная прога не работала, либо робот шёл не туда, куда надо, либо шел куда надо, но не оптимальным способом, либо учителю не нравился сам код...
В общем, с программированием не сложилось :)
у нас была "черепашка" и "робот-пылесос". робот нужно было программировать на русском. это был 6й класс и я обожал это дело, тогда и влюбился в программирование окончательно :)
А у нас вообще не было компьютеров.
Половина комментаторов пропустили важную часть условия и умничают. Всё, что нужно знать о комментаторах
с чего-то вдруг было принято, что если квадрат 1 на 1, то у робота 1 путь, хотя на самом деле пути нет, а не он пустой, т.к. робот никуда не движется. Дальше можно не смотреть, как уже написали в комментах, задача решается гораздо проще исходя из логики и без рекурсии
самое главное в подобных задачах - уметь применять знания полученные при решении. а то приходят литкодовцы и кроме алго и систем дизайн интервью ничего пройти не могут. да и на практике говнокод лютейший генерируют. идея которая была заложена в алго интервью уже изжила себя и это абузят все кому не лень.
Можно свести задачу к графу, построить матрицу смежности и возвести в степень k, где k - расстояние между вершинами. Это будет где-то (m*n)^2.5 сложность, зато потенциально найдет решение в общем лучае. + Будет задел на применение прочих графовских алгоритмов
Можно решить задачу через комбинаторику и найти ответ в одну строчку вычислений)
@@alexanderpalagin4662на больших 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]);
Да уж, уже подзабыл программирование со школьных лет не занимался
Хороший контент, жаль что Саша канал забросил.
Обход шахматной доски конем куда сложнее рекурсия. Автору респект.
Решал такую задачу много лет назад на позицию джуна
2001 год. У нас тогда появился компьютерный класс в школе и на информатике мы писали программу с похожим решением. Только там был не робот, а кенгуру.
Если кенгуру - тогда m-n заменяем на k-z . Только так и не как иначе!
@@maksimr3175 а для черепашки x-y
@@A1bertG шуточки шутим?! Какие "ХУ"? Ну какие ху? Какие ху. Это элементарно ! Если черепашка значит n-z !
Шучу. Всех благ! Кидаю краба. Присел на корточки. Семечки плюю в кулёчек .
Пока такие задачи задают на собеседованиях в гугл и амазон - у нас их добавляют в ЕГЭ по информатике))
Иначе некому в гугле будет работать. Вы же не думаете, что таланты из Стэнфорда пойдут в Гугл работать? Такие идут работать в более важные стратегические структуры.
Контент супер!
_Динамическое программирование_ - способ решения сложных задач путём разбиения их на более простые подзадачи.
Вся наша жизнь немножно динамическое программирование :-)
Видео как бы намекает зачем компьютеру надо столько много памяти (на стек вызовов рекурсии, на массив для мемоизации) :-)
Тут много людей пишет в комментариях, что можно решить оптимальнее и аналитически вообще (сведя к формуле), но если хорошенько подумать, то показана то не конкретная задача, а _класс_ задач.
Ну и опять же, компьютер изобрели чтобы НЕ заморачиваться. Да, можно интеграл красиво аналитически посчитать, а можно методом трапеций численно.
Аналитически это конечно же красиво и "интеллектуально элитно", но в суровой реальной жизни когда заказчику надо "вчера!" и результат нужен "прям щас и один раз!" и "уже всё!" и у директора дёргается от этого глаз от нервов всех этих - математика-аналитика-теоретика раньше уволят нафиг (и заводу может кирдык придёт), ну или премию дадут "Петровичу" который методом трапеций за 5 минут прикинул и сказал "ах**но! материала хватит! вот смета!" :-))))
Разве математик-теоретик не посчитает интеграл по красоте сейчас 5минут?
@@akiiaev математик-теоретик - товар штучный, а решения надо принимать много где, и тут на помощь придёт "числодробилка" которая сделает даже дурачка "великим математиком" ;-)
в мире много рукожопов - поэтому изобрели санчала трафареты, а потом и ЧПУ станки, в мире много тугодумов - поэтому изобрели компы и численные методы и методы мат.моделирования. и это дало возможность даже дурачкам кормиться и размножаться, алилуйя! :-D
но конечно же "для любителей помучаться" (мазохистов) остались ручные дрели, лобзики, логарифмические линейки, кульманы для чертежей вручную и прочие "орудия пыток" :-D
но мне как-то нравится в 3D принтер или ЧПУ загружать чертёж, который я могу поправить в САПР если что не переделывая полностью. видимо я не дошёл до "дзена", мне результат как-то важнее процесса.
Примерно в этом и заключается талант грамотного технического менеджера: отличать задачи, которые нужно решать быстро и в лоб, от тех, которые нужно решать долго и красиво. И в промышленной разработке, конечно, первых гораздо больше, но всё же не 100 %.
вот легче решение для понимания. Если идем вправо на одну клетку тогда это приравниваем к 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 для первой итд
Фильм "Куб" вспоминается. Разница в том, что в случае ошибки в гугл тебя не убьют)
Я долго думал, что же мне напоминает ДП. Это как кэширование данных, чтобы не приходилось каждый раз обращаться к базе
Вроде все понятно и просто ,но если самостоятельно сделать ,я бы прикурил )
Для относительно небольших размеров грида самым быстрым решением будет формула биномиальных коэффициентов, так по использованию памяти мы получим O(1)
там формула еще проще
@Mike я не считал максимальный грид для моего решения, но для решения на литкоде мне хватило трёх переменных long long и небольшой оптимизации. В итоге самый быстрый результат на сайте.
Разве формула биноминальных коэффициентов даёт О(1).
Там же, кажется, О(n)
@@avshukan ты не совсем прав, фактически нам нужна петля для подсчёта факториала, но при минимальном упрощении мы считаем только то колличество итераций, которое будет меньше (k!-1 Или (n-k)! -1)
@@adventurer_v
ну, то есть O( min(k, n-k) )
в худшем случае, это О(n/2)
так?
Нужно отвечать "ок, гугл". Вы нам не подоходите.
рекурсия это - зло (в большинстве случаев)
всегда нужно быть ОЧЕНЬ осторожным с рекурсией (а лучше избегать ее), т.к. очень часто неизвестна глубина рекурсии и размер стека, а отсюда и до переполнения стека недалеко (если конечно современным прогерам известно что это такое :) )
Это утверждение верно, если язык не поддерживает TCO и ленивые вычисления (если, конечно, противникам рекурсии известно что это такое :) )
@@MultiOpachki
противники рекурсии любят писать переносимый код, который не зависит от платформы, компилятора, настроек, ... :()
кстати даже не хочу знать что такое ленивые вычисления, хотя догадываюсь
зато хорошо знаю как сложно найти переполнение стека, которое происходит раз в 5 лет у одного юзера из 1000
@@alexeyivanov3222 Настолко переносимые, что эти программы запускаются еще и на AVR, например? Чтож, похвально.
1) а. С массивом будет вызываться функция повторно для тех клеток, которые равны нулю; б. Массив должен быть заранее известного размера либо динамически перераспределяться - будет развесистый спагетти-код. Поэтому надо функцию вызывать из экземпляра класса, добавить поле с мапой и в начале функции ифчик с проверкой на присутствие в мапе, а в конце добавить вхождение в мапу. 2) a. рекурсия сама по себе ограничивает глубину вызова и стоит это как-то учесть, например, выбрасывать исключение при слишком больших (m, n); б. Ддя больших значений m и n, которые не позволят массиву/мапе поместиться в кэш процессора, будет производится вычитка из памяти. Операция эта долгая, и прежде чем добавлять такую реализацию, стоит проверить на бенчмарках выигрыш от нее - вполне возможно, что повторное вычисление будет быстрее
По сути массив вы используете как мапу, где индекс == ключу элемента. Согласен, для оптимизации это хорошо иногда работает, массив очень полезная штука, но тут и мапа будет хорошо работать, а читаемость существенно вырастет, поэтому она и должна быть в коде как минимум до того момента, пока на бенчмарках не будет доказана эффективность замены
@@hro688 обычно мапа на порядки медленнее массива...
@@user-uvk в цифрах О большого и то, и то О(1). Понятно, что будут накладные расходы на высчитывание хэша и сравнение объектов, а также на плохо распределяемые объекты, но и в таком случае, например, в джаве, все под капотом достаточно хорошо оптимизируется до O(log N) для сравнимых элементов. И при этом по памяти мы независим от непрерывного участка памяти. В общем, непонятно, откуда взялось "на порядок медленнее", можете пояснить? И в каких компаниях попросили бы писать такой код без мапы (чтобы туда не попасть случайно), если, конечно, там не какую-нибудь встроенную систему реального времени управления атомным реактором внутри него же самого на жестко ограниченном железе пишут
@@hro688 Мапа работает гораздо дольше по следующим причинам: 1) при вставке очередного элемента под него надо выделить память. Это значит, пройтись по спискам свободной памяти, найти там подходящий участок, разделить его на выделяемую и оставляемую в свободной памяти части, организовать необходимые служебные структуры и т.п. 2) из-за наличия служебных полей (от списков памяти) размер выделяемой под элемент памяти больше размера элемента данных. Если элемент данных маленький (как в данной задаче 4 байта), то эти накладные расходы (минимум 2 указателя по 8 байт) в разы больше полезной памяти - это повышает нагрузку на кеш процессора (точнее, снижает вероятность найти данные в нём). 3) при выборке надо посчитать хеш-код, использовать его как индекс в обычном линейном массиве или для поиска по дереву (зависит от реализации мапы) - это требует много машинных команд да ещё с условными переходами (которые имеют свои накладные расходы для процессора), а получение int из простого массива - одна машинная команда. 4) работа с мапой, обычно, это вызовы встроенных функций из библиотеки, а с массивом - прямой код в программе. Это означает лишние обращения к памяти для передачи аргументов подпрограмме через стек, которых нет в работе с массивом.
Мапа имеет огромное преимущество, когда только малая часть возможных ключей (которые могли бы быть индексами в массиве) будет использована. Тут она экономит память, что при больших размерах массива может быть важно. И в случае, когда ключ поиска не может быть напрямую использован как индекс массива, массив отдыхает.
Саша , отлично объясняешь! Хоть я и вообще не хочу быть программистом )) Я пилот, но умение рассказывать у вас однозначно есть!
Ну так, пілоти то раза 2 більше, в середньому, отримують)
@@denisdragomirik не в деньгах счастье
@@pilotjenya тоді давай до нас ;)
@@denisdragomirik нi. Спасибо :)) мэнi и тут дуже гарно
@@pilotjenya 😁😁
Всегда думал, что динамическое программирование это нечто крутое. А оказывается это просто кэш данных?
Интересно кто это применил это на практике больше одного раза?
Все проще. Это треугольник паскаля.
Время работы О(2*(m + n))
В случае если n>=2 и m >=2 ответ записывается формулой
(n + m - 2)!/((m - 1)! * (n - 1)!) //просто найти факториалы отдельно и посчитать
Иначе ответ 1
Думаю лучше было бы использовать вместо робота монстра из корпорации монстров😄
У тех, кто не ищет лёгких путей, может быть ещё один путь: вверх, вправо, вниз, вправо, вверх.
Вот она деградация программистов - писать целую программу для элементарной задачки по комбинаторике
Не все изучали комбинаторику
@@A1bertG Может еще арифметику тоже не обязательно программисту знать?
@@A1bertG Это школьная программа. Что этот программист вообще изучал?
Кликбейтное видео, вот и всё. Даже если и спрашивали в гуглах такое, то только из-за нехватки программистов
Сам автор тоже алгоритмы нифига не знает. o(2^(n+m)) это же ужасно. Не сложно додуматься до o(1), просто выводя формулу
Пробовал данное решение использовать на 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]
};
Динамическое программирование здесь понадобилось бы, если бы были случайно разбросаны острова, которые бы случайно вырезали часть маршрутов. А в задаче именно в таком виде тут будет чисто комбинаторное решение в виде функции от m,n, равной числу сочетаний из (n + m - 2) по (n - 1) или (m - 1), без разницы
Подскажите пожалуйста, как выводится такая формула и почему для данной задачи? Заранее спасибо.
@@zugzug90 Оно не выводится, оно по смыслу есть) У тебя путь длиной n + m - 2 в котором ты делаешь (m -1) шагов вниз и (n - 1) шагов в сторону. Ну то есть условно можно представить путь как последовательность из 0 и 1 длиной (n + m - 2) в которой будет(n - 1) нулей и (m - 1) единиц, располагающихся в случайном порядке. Тогда совсем очевидно что количество таких перестановок будет числом сочетаний кол-ва нулей или единиц из всей длины
@@matanmaster "ты делаешь (m -1) шагов вниз" - но ведь вниз ходить нельзя.. Все таки непонятно, как получается (n-m-2).. Мб (n + m - 2) ? Там и выше у вас такое число кстати. Комбинаторику уже совсем не помню, пока что утверждение для меня неочевидно, но вероятно если освежить в голове пару глав - станет понятно лично мне. В любом случае спасибо за разъяснения.
@@zugzug90 Ну в данном ролике вверх, обычно в этой задаче идут из верхнего левого в нижний правый. (n - m - 2) и нет нигде, там сумма.
Только функция 2^(m*n) - показательная, а не экспонента.
Спасибо за видео!
☦❤
Странный алгоритм - показывает 3 пути когда их 4 в последнем примере. Через центр идут 2 пути один вверх, другой вниз
Интересно почему мало кто обратил на это внимание.
Как это вниз? 0:17 Условия задачи гласят, что робот не может так ходить.
@@MuKeXa ясно. странный алгоритм для странного робота)
Чем-то напоминает задачи из ЕГЭ
Странно, что это было задачей в гугле, хотя это из егэ
Тоже смотрел и думал - я же это решал в 11 классе. Какой гугл? Да, про сложность алгоритмов узнал на 1-2 курсе. Сохранение результатов в какой-то промежуточный буфер - не сказать что какая-то гениальная оптимизация.
Да. Подобная этой задача была в егэ.Только её по другому подавали. Возможно мы говорим про разные задачи,вы скорее всего имеете ввиду 18-на робота,но я имел ввиду номер 22-на траекторию.Условия задачи очень просты и даже сложнее этой задачи,суть в том ,что есть ходы,старт и финиш.Например нужно получить из цифры 6 число 76 используя ходы +2 и *2.И нужно просчитать сколько вариантов имеется.Я решал её программированием и это было даже легче, чем я думал.Я без абсолютной оптимизации запускал перебор двоичного кода,сейчас объясню.Суть в том,что я искал самый маленький ход - то есть тот ход(из условия задачи),который увеличивает старт на минимум.После этого считал наибольшее количество данных мелких ходов,чтобы достичь финиша.Это и есть максимальная длинна ходов,то есть больше уже не может быть.Например,есть ходы +1 и +2 и нужно из 2 получить 10.Тогда самый мелкий ход+1 и мне понадобиться 8 раз его применить.Это и есть максимальное количество ходов.Больше 8 ходов не может быть.Это первый шаг. вторым шагом нужно определить сколько у нас всего видов ходов(из условия задачи).Например если есть ходы +1 и +2,то мы будем работать в двоичной системе счисления,где 0 это +1,а 1 это +2.Таким образом последовательность команд 11111111 это многократное прибавление 1 к старту и при этом самое длинная .Отсюда переводим эту максимальную по значению и по длине цепочку в 10сс(на самом деле не надо я для объяснения сделаю так). И тогда получается,что перебор вариантов мы запускаем от 0 до этого числа.И так переберутся все варианты команд.Просто потом проверяем на условия дошли ли до финиша и прибавляем к отдельной переменной 1.По факту строчек кода не на много больше.А зная нужные библиотеки даже меньше. И тут уже я думаю вы догадались,что если бы ходов было 3,то мы бы работали в троичной сс,где 0 - первый ход,1-второй ход,2-третий ход.И мы перебираем этот троичный код с различными условиями.Если идею поняли ,то додумаетесь сами)))Таким способом можно было решить и эту задачу,но я не думаю,что гугл оценит перебор вариантов.
В общем суть поняли,дальше есть небольшие приколдесы,потом поймёте о чём я если запрогаете это.Приколы типа, а как же начать последовательность команд с 0 в двоичном коде,хотя у вас всегда с 1 начинается 2ичный код итд.Кто ничего не понял смотрите видео и не ебите себе мозги как я ебал себе в 11 классе,чтобы решить 22номер,но это дало свои плоды. Кому интересно есть пару задач,которые интересно запрогать,поэтому,если захотите поебать мозги ,обращайтесь,озадачу вас)))
@Vlad Balabkin я имел в виду, что додуматься до сохранения результата вместо кучи повторных вычислений может если не любой школьник, то любой студент из околоайтишных направлений. На "задачу из гугла" это совсем не тянет. Про эффективность это ты сам себе придумал, я такого не говорил.
@@parasha7220 Дык это ж обычная ДП-шка
Решение за константное время O(1):
(n+m-2)!/((m-1)!(n-1)!)
Хорошо объясняешь. Но почему так мало видео?
Пашет человек на гугл/амазон/фейсбук, некогда
по моему задача решается легче математически. всего шагов n+m-2 и надо выбрать лишь номер шагов вверх или вправо, тоесть ответ С из n-1 по n+m-2 или C из m-1 по n+m-2 тут как удобнее, т.к. числа эти будут равны
Задача не на ДП, она бьётся формулой. Ясно, что будет сделан m + n -2 ход, из них n - 1 будет вверх. Легко понять, что число маршрутов равно числу способов выбрать из m + n - 2 мест под проход вверх ровно n-1, это сшка из математики. Такую ц-шку можно посчитать за линию (то есть О(m+n)), что быстрее дп, так как дп предполагает сложность O(m*n).
Это раздел математики именуемый "комбинаторика".
Вот он и занимается изучением этого вопроса. Ну и вцелом давно изучили уже.
поверните треугольник Паскаля
эту задачу можно решить гораздо проще и красивее, без циклов, условий и прочего. можно составить формулу числа возможных путей от N и M ) вот как это можно сделать: с каждым ходом робот продвигается либо вверх либо вправо, следовательно все маршруты имеют одинаковую длину и отличаются только последовательностью ходов вверх и вправо, количество ходов вверх = N-1 количество ходов вправо = M-1. наша задача - найти, сколько есть вариантов расставить N "вещей" в (N+M-2) позициях ("вещи" не уникальны). для этого есть формула в комбинаторике. помогите мне её вспомнить))))
опять же, это красивее, но дольше обрабатывать, так как вычисление условного поля 2000х2000 это затратнее
Добрый день. Можно ли решить задачу следующим способом? Робот может двигаться только вправо и вверх, т.е. каждая клетка из которой можно двинуться вправо или вверх является развилкой и дает +1 путь - это не крайние правые и не крайние верхние клетки. При поле размером 1 клетка в ширину или 1 клетка в высоту у робота только один путь. Т.о. получаем алгоритм: h=5; n=4; ways_count=1; hi=1; ni=1; for(hi=1;hi++;hi
Развилка даёт не +1 путь, а +к путей , где к - количество путей до этой клетки.
Проверьте сами себя: посчитайте для квадрата 4*5 "руками" (должно получиться 35) и своим алгоритмом
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)
Аналогичный алгоритм на питоне
Что бы решить эту задачу нужно думать как робот 😆
Да, у компьютера (робота) есть одно преимущество: он может рекурсию быстро проделать (и даже полный перебор, но рекурсия лучше), то есть "провести мысленный эксперимент" быстрее человека. Для того собственно computer ("вычислитель" в переводе) и изобрели!
Я вот больше "древним людям" поражаюсь - такое считали на бумажке, такие алгоритмы изобретали - уму непостижимо! А сейчас щёлк-щёлк и полным перебором "в лоб" школьник задачу решает с помощью компьютера как "числодробилки". Заставляет задуматься "а прогресс ли?" в плане человечества... :-)
Отупление в степени бесконечность!!
Можно решить задачу представив клетки в виде бинома Ньютона
Это ж бином Ньютона :)
Вот решение в три строки:
factorial = lambda n: 1 if n == 0 else n * factorial(n-1)
def calculate(m, n):
return factorial(m+n-2) // factorial(m-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
На 8:12 можно проверять выражение на равенство нулю и возвращать значение из массива ниже
Сэкономим целую строчку😅