Простое, оптимизированное решение популярного вопроса об алгоритмах.

Проблема

Уникальные Пути можно найти на литкоде здесь.

На сетке 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-битного максимального целочисленного значения.

Я написал эту статью, потому что хотел улучшить свое понимание этой проблемы. Надеюсь, я помог улучшить и ваше понимание этого.

Спасибо за чтение!