Простое, оптимизированное решение популярного вопроса об алгоритмах.
Проблема
Уникальные Пути можно найти на литкоде здесь.
На сетке m x n
стоит робот. Изначально робот находится в верхнем левом углу (т. е. grid[0][0]
). Робот пытается переместиться в правый нижний угол (т. е. grid[m - 1][n - 1]
). Робот может двигаться только вниз или вправо в любой момент времени.
Имея два целых числа m
и n
, верните количество возможных уникальных путей, по которым робот может добраться до правого нижнего угла.
В этом примере у нас есть сетка 3 x 7. m = 3, n = 7
У робота есть 28 уникальных путей, чтобы добраться до «финиша», только двигаясь вправо и вниз.
Каждый случай, кроме одного, имел бы бесконечное число решений, если бы робот также мог двигаться вверх или влево. Ты знаешь почему? Вы знаете пограничный случай?
Решение
Когда я впервые столкнулся с этой проблемой, моей первой мыслью было построить матрицу, а затем подсчитать все возможные пути с помощью рекурсии. Я быстро понял, что это будет не очень эффективно с точки зрения пространственной или временной сложности.
Затем я подумал: «Должен быть какой-то способ решить это с помощью математики».
Чтобы робот добрался до финиша, ему нужно переместиться в общей сложности на m-1
делений вниз и на n-1
делений вправо. Итак, если m = 3
и n = 7
, это один из возможных путей:
DDRRRRRR
Где R
представляет движение вправо, а D
представляет движение вниз. Так что на самом деле все, что нам нужно сделать, это найти все перестановки этой «строки».
Количество уникальных перестановок слова с x
буквами равно x!
или x факториалу. Это при условии, что в слове нет повторяющихся букв.
Для каждой буквы в слове эта цифра x!
делится на произведение частоты каждой буквы факториала. Получается факториал x!
для слова со строго уникальными буквами, потому что 1! = 1
. Но для слова «мир» получается 5! / (1! * 2! * 1! * 1!)
или 5! / 2!
.
Для этой задачи уникальных путей длина слова равна m-1 + n-1
. И мы знаем, что есть две буквы, D
и R
, и что они имеют частоту m-1
и n-1
соответственно. Итак, окончательное решение:
m--; n--; (m + n)! / (m! * n!);
Вот как это выглядит на TypeScript:
function uniquePaths(m: number, n: number): number { m--; n--; let result = factorial(m + n) / (factorial(m) * factorial(n)); return result; } function factorial(num: number): number { let product = 1; while (num > 0) { product *= num; num--; } return product; }
Примечание. Если язык, на котором вы пытаетесь решить эту задачу, имеет собственную встроенную функцию факториала, я рекомендую использовать ее. Я уверен, что это более эффективно, чем то, что у меня есть здесь.
Фактически, я предполагаю, что встроенные факториальные функции на уровнях программирования высокого уровня могут быть O (1), сохраняя результаты и выполняя поиск. Вы, вероятно, даже не доберетесь до 20 факториала, пока не достигнете даже 64-битного максимального целочисленного значения.
Я написал эту статью, потому что хотел улучшить свое понимание этой проблемы. Надеюсь, я помог улучшить и ваше понимание этого.
Спасибо за чтение!