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

[@sashalukin]

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

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

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

[@ovsyannikovo]

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

[@apristen]

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

[@ВиталийЯрмыш-х2к]

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

[@РупорК]

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

[@ВиталийЯрмыш-х2к]

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

[@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]

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

[@Ingvar_konge]

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

[@ИмяФамилия-э4ф7в]

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

[@revingar]

​@@ИмяФамилия-э4ф7в, видимо закончил

[@axiswait5339]

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

[@vb7038]

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

[@ВиталийСлавин-й6о]

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

[@alexeys1789]

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

[@GatherOwsen]

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

[@alexeys1789]

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

[@volervagashim]

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

[@alexeys1789]

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

[@volervagashim]

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

[@iGavelyuk]

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

[@AWoh51EIbvd]

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

[@AWoh51EIbvd]

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

[@AWoh51EIbvd]

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

[@iGavelyuk]

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

[@denisdragomirik]

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

[@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]

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

[@unformedvoid2223]

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

[@learpcss9569]

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

[@sashalukin]

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

[@cdeblog]

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

[@antonpetrenko9176]

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

[@СергейДавтян-щ1и]

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

[@leonovgleb8535]

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

[@JohnnyIntoHell]

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

[@Aneugene]

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

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

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

[@Aimilomim]

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

[@ConstantinKubrakov]

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

[@polipavlovich4586]

Спасибо большое за объяснение!

[@dorokhovea]

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

[@Leonard_Gray]

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

[@iGavelyuk]

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

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

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

[@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 функций пока они не дойдут до робота, а сразу возвращает единицу.

[@firejvlz]

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

[@cleverabbit]

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

[@firejvlz]

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

[@cleverabbit]

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

[@mishaYehrashkin]

Спасибо! Интересный разбор задачи!

[@etaraba9385]

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

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

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

[@avshukan]

Плюсую

[@NightFrostDevil]

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

[@YevhenDiulin]

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

[@АндрейБочарников-х5ъ]

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

[@YevhenDiulin]

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

[@freedomtv2295]

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

[@YevhenDiulin]

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

[@freedomtv2295]

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

[@karfagen86]

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

[@nikitafamily5341]

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

[@___p_y_c_u_4___470]

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

[@surekt4780]

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

[@___p_y_c_u_4___470]

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

[@evgeniym9134]

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

[@nanoIX9]

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

[@ilnar129]

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

[@apristen]

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

[@akiiaev]

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

[@apristen]

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

[@vryaboshapko]

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

[@АуАУауАнрп]

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

[@sashalukin]

Спасибо!

[@АуАУауАнрп]

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

[@zelmanfeig5404]

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

[@АуАУауАнрп]

@@zelmanfeig5404 и что?

[@АуАУауАнрп]

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

[@scruper]

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

[@denispetrovich3039]

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

[@airn587]

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

[@denispetrovich3039]

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

[@АнтонФролов-о1с]

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

[@denispetrovich3039]

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

[@denispetrovich3039]

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

[@dm_www9360]

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

[@GrAlUnrealEngine]

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

[@vitpvs8062]

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

[@ovsyannikovo]

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

[@GrAlUnrealEngine]

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

[@ovsyannikovo]

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

[@GrAlUnrealEngine]

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

[@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]

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

[@АлександрШ-й5ж]

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

[@DaemonHK666]

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

[@enott]

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

[@vitall789]

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

[@кикислав]

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

[@ДенисСитник-й8б]

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

[@АкрилГуашев]

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

[@кикислав]

@@АкрилГуашев Там факториал от n+m

[@АкрилГуашев]

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

[@кикислав]

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

[@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) и своим алгоритмом

[@iwanttobealihgt]

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

[@АлексейРеволюция]

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

[@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 для первой итд

[@АндрейЯкимов-п2щ]

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

[@ГригорийДима-ж7б]

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

[@Igril]

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

[@rizhiy87]

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

[@Igril]

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

[@ojer101]

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

[@ojer101]

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

[@Юрий-о4х5й]

А почему массив выделяется m+1 на n+1 а не просто m на n?

[@Ноунеймбезгалочки-м7ч]

мне кажется или просто return n+m-2?

[@volervagashim]

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

[@BizzaroFukuro]

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

[@pahom2]

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

[@anonsd5521]

Решила в голове за пять секунд. Решение: ```cpp unsigned long long coolfunc(int a, int b) { int n = a+b-2; int k = (n+1)/2; return binomial(n,k); } ``` Для решения нужно будет округление и факториалы и биномиальные коэффициенты, их можете взять из библиотеки или сами написать: ```cpp #include #include void reduceFraction(int &numerator, int &denominator) { int greatestCommonDivisor = std::gcd(numerator, denominator); numerator /= greatestCommonDivisor; denominator /= greatestCommonDivisor; } int factorial(int num, int k=1) { if (num

[@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) так?

[@mikepolo6734]

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

[@DeadBuddy01]

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

[@Tess7490]

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

[@airn587]

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

[@diogen8443]

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

[@Aimilomim]

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

[@ukrainekiev3990]

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

[@Aimilomim]

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

[@ukrainekiev3990]

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

[@Aimilomim]

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

[@seagray69]

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

[@lone9724]

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

[@pilotjenya]

Саша , отлично объясняешь! Хоть я и вообще не хочу быть программистом )) Я пилот, но умение рассказывать у вас однозначно есть!

[@denisdragomirik]

Ну так, пілоти то раза 2 більше, в середньому, отримують)

[@pilotjenya]

@@denisdragomirik не в деньгах счастье

[@denisdragomirik]

@@pilotjenya тоді давай до нас ;)

[@pilotjenya]

@@denisdragomirik нi. Спасибо :)) мэнi и тут дуже гарно

[@denisdragomirik]

@@pilotjenya 😁😁

[@pangimoon4789]

Саша, в итоге устроился куда-нибудь на работу?

[@krotus84]

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

[@Voprosik102]

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

[@понятныйрепетитор]

А через комбинаторику?

[@Guapter]

Мне одному кажется странным код, который он приводит? Во первых нигде нет суммирования значений рекурсивных ступеней(Везде только ретёрны), во вторых функция должна возвращать инт, а возвращает массив. 8:12

[@pu0081]

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

[@alexrbh9515]

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

[@vadimgusev724]

Я может что то не понял, но в примере где n=3, m=2, 4 правильных ответа, а не 3

[@m1stakk3]

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

[@egorpetrov2877]

робот не умеет ходить вниз

[@chaosvk13]

вверх вправо вправо вправо вверх вправо вправо вправо вверх

[@Djonni47]

@@chaosvk13 А как же маршрут "вверх вправо вниз вправо вверх"?

[@chaosvk13]

@@Djonni47 3 комментария вверх

[@redflower9323]

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

[@chillappreciator885]

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

[@Anton-dl7me]

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

[@SuhininAlex]

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

[@fifa1183]

А почему мы не можем в первой задачи пойти так ( 2,1; 2,2; 1,2; 1,3 м следующий ход уже в дверь ) это был бы 4 вариант

[@Gregory-vc2vs]

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

[@alexanderpalagin4662]

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

[@abcdefghi1489]

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

[@likalucky]

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

[@xender2112]

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

[@sergiik2168]

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

[@A1bertG]

Не все изучали комбинаторику

[@xalgor]

@@A1bertG Может еще арифметику тоже не обязательно программисту знать?

[@mykhaylobatalinskyy3982]

@@A1bertG Это школьная программа. Что этот программист вообще изучал?

[@普京的手机]

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

[@普京的手机]

Сам автор тоже алгоритмы нифига не знает. o(2^(n+m)) это же ужасно. Не сложно додуматься до o(1), просто выводя формулу

[@РоманСапин]

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

[@MuKeXa]

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

[@andreycanon8929]

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

[@maksimr3175]

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

[@A1bertG]

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

[@maksimr3175]

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

[@aleksandrzhadetsky2535]

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

[@ГлебАстафуров]

Можно сразу дать ответ: С из n+m по n.

[@avshukan]

Ну так надо это ещё посчитать. Можно O(n*m), а можно O(n)

[@dfdghyuiopoiuhgvfghjo]

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

[@toxic-text]

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

[@CyanideBtm]

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

[@ДмитрийСкоринов-и2ц]

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

[@justaniceguy7293]

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

[@vadimpetruhanov4150]

Да, можно решить просто через число сочетаний С_(n+m - 2)^(n - 1), но автор показывает более понятный для программиста итеративный рекуррентный способ

[@easy_smoke]

Программирование попросту немного не про то, там недостаточно один раз вычислить по формуле и забыть. Что если, отныне нужно считать наикратчайший из этих путей? Или у ячеек вдруг появились веса (ходить по одним "дороже", чем по другим)? Гораздо проще ввести небольшие изменения в текущий алгоритм, чем выводить новые формулы. А если этот алгоритм работает в рамках какого нибудь приложения и с этим кодом взаимодействуют другие разработчики? Тогда для его понимания проще и быстрее пару раз прогнать этот кусок кода с разными значениями, нежели разбираться что такое биномиальный коэффициент. Так что, этот вариант имеет место быть, но в мире программистов - это очень плохая практика

[@rostislavbolyachev729]

@@easy_smoke плохая практика не использовать математику для уменшения усилий на вычисление

[@easy_smoke]

У вас явно не было серьёзного опыта в продакшне. Написать программу это лишь небольшая часть работы, гораздо бОльшая - её поддержка. Грош цена коду, если нельзя с ходу понять что и как он делает, а в последствии адаптировать его под меняющиеся условия. Поэтому важнее оптимизировать процессы в команде и сэкономить человекочасы, нежели подобные мелочи, а современные вычислительные мощности всё равно нивилируют разницу до минимума. Конечно, если мы запускаем аппарат в космос, математика сразу выглядит в разы выигрышнее. Условия всё равно концептуально не меняются, а сложность вычисления минимальная. Однако, с IT это уже имеет мало общего

[@rostislavbolyachev729]

@@easy_smoke видимо у вас его еще меньше, особенно в высоконагруженных😅

[@alexeyivanov3222]

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

[@MultiOpachki]

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

[@alexeyivanov3222]

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

[@MultiOpachki]

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

[@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

[@maxpayne5044]

Странный алгоритм - показывает 3 пути когда их 4 в последнем примере. Через центр идут 2 пути один вверх, другой вниз

[@BUTEK1981]

Интересно почему мало кто обратил на это внимание.

[@MuKeXa]

Как это вниз? 0:17 Условия задачи гласят, что робот не может так ходить.

[@maxpayne5044]

@@MuKeXa ясно. странный алгоритм для странного робота)

[@СтаниславМаяцкий-д1ы]

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

[@НиколайОлиниченко]

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

[@Сашагарматний]

А можна на нормальній мові?

[@3qa]

Проблемы с условием? Робот может выбрать не кратчайший путь и идти змейкой, что поломает логику

[@fruktiliyagoda]

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

[@freehck]

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

[@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) и нет нигде, там сумма.

[@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) Аналогичный алгоритм на питоне

[@andreikarpiouk9047]

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

[@alexkuznetsov9008]

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

[@АндрейБочарников-х5ъ]

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

[@goldstein1]

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

[@abylayamanbayev8403]

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

[@hro688]

1) а. С массивом будет вызываться функция повторно для тех клеток, которые равны нулю; б. Массив должен быть заранее известного размера либо динамически перераспределяться - будет развесистый спагетти-код. Поэтому надо функцию вызывать из экземпляра класса, добавить поле с мапой и в начале функции ифчик с проверкой на присутствие в мапе, а в конце добавить вхождение в мапу. 2) a. рекурсия сама по себе ограничивает глубину вызова и стоит это как-то учесть, например, выбрасывать исключение при слишком больших (m, n); б. Ддя больших значений m и n, которые не позволят массиву/мапе поместиться в кэш процессора, будет производится вычитка из памяти. Операция эта долгая, и прежде чем добавлять такую реализацию, стоит проверить на бенчмарках выигрыш от нее - вполне возможно, что повторное вычисление будет быстрее

[@hro688]

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

[@user-uvk]

@@hro688 обычно мапа на порядки медленнее массива...

[@hro688]

@@user-uvk в цифрах О большого и то, и то О(1). Понятно, что будут накладные расходы на высчитывание хэша и сравнение объектов, а также на плохо распределяемые объекты, но и в таком случае, например, в джаве, все под капотом достаточно хорошо оптимизируется до O(log N) для сравнимых элементов. И при этом по памяти мы независим от непрерывного участка памяти. В общем, непонятно, откуда взялось "на порядок медленнее", можете пояснить? И в каких компаниях попросили бы писать такой код без мапы (чтобы туда не попасть случайно), если, конечно, там не какую-нибудь встроенную систему реального времени управления атомным реактором внутри него же самого на жестко ограниченном железе пишут

[@user-uvk]

@@hro688 Мапа работает гораздо дольше по следующим причинам: 1) при вставке очередного элемента под него надо выделить память. Это значит, пройтись по спискам свободной памяти, найти там подходящий участок, разделить его на выделяемую и оставляемую в свободной памяти части, организовать необходимые служебные структуры и т.п. 2) из-за наличия служебных полей (от списков памяти) размер выделяемой под элемент памяти больше размера элемента данных. Если элемент данных маленький (как в данной задаче 4 байта), то эти накладные расходы (минимум 2 указателя по 8 байт) в разы больше полезной памяти - это повышает нагрузку на кеш процессора (точнее, снижает вероятность найти данные в нём). 3) при выборке надо посчитать хеш-код, использовать его как индекс в обычном линейном массиве или для поиска по дереву (зависит от реализации мапы) - это требует много машинных команд да ещё с условными переходами (которые имеют свои накладные расходы для процессора), а получение int из простого массива - одна машинная команда. 4) работа с мапой, обычно, это вызовы встроенных функций из библиотеки, а с массивом - прямой код в программе. Это означает лишние обращения к памяти для передачи аргументов подпрограмме через стек, которых нет в работе с массивом. Мапа имеет огромное преимущество, когда только малая часть возможных ключей (которые могли бы быть индексами в массиве) будет использована. Тут она экономит память, что при больших размерах массива может быть важно. И в случае, когда ключ поиска не может быть напрямую использован как индекс массива, массив отдыхает.

[@belmax26]

4 же пути в клетках 2х3, какие 3 пути?

[@mishaamfit5247]

Вниз не ходит так что 3 пути

[@belmax26]

@@mishaamfit5247 тогда да

[@tomahawk777]

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

[@mrposeidon2813]

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

[@gregorashf]

И куда вы пропали?