Всем привет, сегодня мы будем решать вот такую задачку. Нужно определить количество возможных путей, которые может пройти робот до цели. Идти он может только вправо и вниз.
Примеры:
Задача вроде не сложная, но чувствую, есть какой-то подвох. Эта задача чем-то мне напоминает ЕГЭ по информатике. Давайте делать.
Начинаем делать задачу. Обдумывание
Нашу задачу можно решить двумя способами:
1. Посчитать пути циклами
2. Вывести математическую формулу
Выводить формулу будет долго и сложно, большинству из вас это смотреть будет не интересно, но зато наш код будет работать быстрее.
Мне бы хотелось попробовать вывести формулу (спойлер: не получится)
Самое простое это провести верхний путь. Если наша таблица будет высотой в 1 клетку, то при любой ширине путь будет 1.
Если же высота таблицы будет 2 клетки, то у нас будет 7 возможных путей, а точнее количество путей будет равно ширине таблицы.
n = width
Но что будет, если высота будет 3? Здесь уже надо подумать. Каждая наша оранжевая линия (обозначил так для удобства) будет нести в себе сумму предыдущих для неё путей. Допустим, до линии, которую я нарисовал, есть только один путь.
До линии, которая начинается с X = 1 (координаты будем считать с 0), к нашей линии можно дойти двумя путями.
А если бы она начиналась с X = 3, то четырьмя путями
Получается, если бы наша таблица была в высоту 3, у нас было бы столько возможных путей:
1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
Что верно, конкретно этот пример нам и представлен в задаче.
Получается, количество наших путей зависит от Y так:
Y = 1 | n = 1
Y = 2 | n = width (width ширина таблицы)
Y = 3 | n = (1 + width)* width/2
По сути формула, которую я написал, это формула суммы арифметической прогрессии, то есть наших 1 + 2 + 3 + 4 + 5 + 6 + 7.
Не пугайтесь, я просто рассматриваю задачу и пытаюсь выявить математические закономерности. Возможно, формулу вывести так и не получится, и придётся писать код через циклы.
Считаем дальше, если высота 4. Получается, до нашей вертикальной красной линии количество путей это сумма предыдущих оранжевых путей. Красная линия, которую я нарисовал, начинается на X = 1, поэтому количество путей до неё это сумма путей до оранжевых линий на X = 0 и X = 1. То есть 1 + 2 = 3.
У красной линии на X = 3, количество путей будет такое: 1 + 2 + 3 + 4 = 10.
И чтобы посчитать все пути для таблицы с высотой 4, нужно сложить все пути до красных вертикальных линий. Это, получается, сумма от суммы.
1 + (1+2) + (1+2+3) + (1+2+3+4) + (1+2+3+4+5) + (1+2+3+4+5+6) + (1+2+3+4+5+6+7) = 84.
Вот сумму от сумм высчитать будет сложнее.
1 + (1+2) + (1+2+3) + (1+2+3+4) + (1+2+3+4+5) + (1+2+3+4+5+6) + (1+2+3+4+5+6+7) = 84.
Вот это я уже не знаю, как считать по формуле, похоже, нам придётся считать через цикл такие суммы.
Ну и конечно же, если у нас будет высота 5, то формула для вертикальной линии на X = 3 будет такая: 1 + (1+(1+2)) + (1+(1+2)+(1+2+3)). Чем дальше я считаю, тем больше пугаюсь всему этому. Я думаю, формулу вывести возможно, но у нас блог по веб-разработке, и мне бы не хотелось вас пугать всеми этими математическими сложностями. Я потрачу кучу времени, а вы просто закроете статью, нет, давайте делать это как-то через код и циклы.
На ум здесь приходят только рекуррентные функции. Мы будем считать количество путей для нижних вертикальных линий. Количество путей к нашей линии это сумма путей к предыдущим линиям. Давайте это как-то пропишем в коде.
Начинаем писать код
Создадим нашу рекуррентную функцию, которая будет складывать эти пути.
Сразу пропишем условие, которое выводит 1, если у нас высота 1.
Для остальных случаев будет работать наша рекуррентная функция. Если наш Y будет 1, тогда до каждой вертикальной линии ряда будет только один возможный путь.
Сделаем переменную для суммирования путей. Сделаем цикл, который добавляет в переменную сумму предыдущих путей.
Но эта рекуррентная функция позволяет определить количество путей до одной вертикальной линии, а нам нужны все вертикальные линии последнего ряда
Суммируем результаты рекуррентной функции в главной функции:
Запускаем...
Наш код отработал правильно. Теперь осталось проверить его на более большом количестве массивов.
И мы столкнулись с проблемой оптимизации. Наш цикл просто не успевает выполнить задачу вовремя
Приступаем к оптимизации
Я так и знал, что нечто такое может произойти.
Так уж получилось, что у нас слишком большая таблица, примерно вот такая. Из за этого наш код не укладывается по времени, поэтому LeetCode завершает его. А мы должны нашим кодом решить все таблицы.
Я хочу сделать так, чтобы после расчёта пути к каждой линии, наши результаты сохранялись, и коду не приходилось рассчитывать всё заново. Это называется кеширование, очень полезная вещь.
Я тут подумал... Самое удобное, где можно хранить такие значения это двумерный массив. Но его нужно сначала заполнить нулями, а потом нужными значениями, а потом эти самые значения ещё и проверять, есть ли они на нужных ячейках или нет. Мне кажется, это будет затратно по вычислительным ресурсам.
Почему бы не сделать вычисление наших путей не снизу, а сразу сверху? Можно сделать двумерный массив и сразу в него записывать нужные значения. Можно отказаться от рекуррентных функций и обычными циклами проходиться по массиву. Тогда мы сильно оптимизируем нашу программу.
Я понимаю, можно было бы сделать так с самого начала, но в своём блоге я хочу показать не только правильные решения, но ещё и процесс моих размышлений. В чём интерес делать сразу всё правильно? А так вы увидите два способа решения этой задачи, так ещё и посмотрите, каким образом я справляюсь с трудностями, как я размышляю и какими способами действую.
Начинаем делать по-новому. Цикл по Y будет проходить m - 1 итерацию, так как на самой первой строчке нечего считать.
На y = 1 просто всё заполним единицами. К каждой вертикальной линии на y = 1 есть только один способ добраться. Именно до вертикальной линии, не до самой ячейки.
После этого делаем ещё один цикл, который будет проходиться по вертикальным линиям, которые стоят на одном X с нашей перебираемой линией и меньше.
Будем суммировать эти пути, а в конце записывать их в нужную ячейку. Я вынес объявление переменной "sumi" за цикл, чтобы она объявилась только один раз, а дальше только меняла значения. Я вынес объявление переменной за цикл, потому что объявлять её в каждой итерации это затратно по ресурсам.
Если что, объявлять переменную в каждой итерации цикла не стоит, для памяти это будет более затратно, чем объявить её один раз вне цикла.
Конечно же, нужно после этого проверять, что же будет выведено в нашем двумерном массиве. Не будем же мы программировать наугад.
Получается у нас что-то вот такое. И это правильно. Нам осталось сложить все цифры из последнего столбца матрицы и вывести их в ответ.
Мы переменную "sumi" можем использовать ещё раз в подсчёте суммы чисел в последней строке. Будем суммировать строку по Y m - 2, потому что наша таблицы в высоту m - 1 строк.
И ответ у нас получился правильный
И с задачей мы справились
Но всё же хочется обогнать других
Приступаем к оптимизации
У меня появилась идея. Мы в начале цикла загружаем пустой массив в массив, который играет в нём роль строки. А потом мы по индексам с ним работаем и туда что-то загружаем.
То есть нашему коду нужно вычислить, где в памяти находится наш массив внутри массива, где находится конец этого массива внутри массива, потом добавить туда число и выполнить какие-то действия.
А если мы каждый раз, после начала кода будем создавать отдельный массив, заполним его и один раз вставим в большой двумерный массив. Это будет менее затратно по времени, чем если мы будем каждый раз менять элементы двумерного массива.
Также в коде я для объявленной в начале "sumi" задал значение 0, чтобы сразу показать JavaScript, что мы работаем с числом, чтобы ему не приходилось менять тип данных в дальнейшем.
Я очень сильно удивлён, но у меня получилось обойти всех и попасть в 100% лучших по скорости кода.
Конечно же, я не верю в это, вероятно у меня какая-нибудь 0,03ms скорость, а у какого-нибудь гения 0,01ms, к примеру. А LeetCode не видит разницы между ними, просто округлил и поставил мне, что я попал в 100% лучших. Тем более при каждом запуске кода, значения могут быть разными.
Допустим, мы перезапустили код
А вот здесь я просто в шоке
Так что LeetCode не очень то и точно определяет, насколько быстро у вас работает код, каждый запуск случайные значения. Но мы можем как-то снизить этот разброс и сделать так, чтобы код работал эффективнее.
А какой смысл считать суммы последней строки и делать это в отдельном цикле?
Можно добавить это в наш цикл и считать сразу там
Только вот после этого у нас происходит ошибка. Это происходит с матрицей 1 на 2, матрица, как столбик. Наш код считает все строчки, кроме первой, а в этой матрице, получается, он посчитает только последнюю ячейку, а она не вызывает условия, где суммируются наши значения.
Это условие нужно поставить ещё и сюда
Опа
А если перезапустить, то так
Нет, я ошибся. В sum нет смысла записывать "row[x]". В одном случае мы можем сразу прибавлять единицы, а в другом "sumi". Это будет ещё быстрее
Хорошо, прекрасно
Подходим к концу
Ну вот и всё, мы смогли решить эту задачку и оптимизировать код до хорошей скорости. Это было интересно, особенно мне понравилось думать над оптимизацией.
Ну а если вам есть, что добавить, пишите в комментарии. Любая конструктивная критика приветствуется.
Ну а вы не забывайте подписываться на канал и ставить лайки 😁