LeetCode 62, подумайте о лучших решениях динамического программирования

алгоритм

Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания


СегодняLeetCode тема 36В статье давайте рассмотрим 62 вопроса LeetCode, Уникальные пути.

смысл названия

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

Смысл этого вопроса очень прост: задан прямоугольный лабиринт, в левом верхнем углу находится робот, а в правом нижнем углу — пункт назначения. Этот робот может идти только вниз или вправо Сколько путей есть у этого робота, чтобы добраться до места назначения?

Этот вопрос очень добросовестный, учитывая условия, длина и ширина прямоугольника не более 100.

Образец 

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Input: m = 7, n = 3
Output: 28

решение

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

Он имеет стандартное решение в стиле шаблона в виде головоломки:

Для точки C на графике количество путей, ведущих к ней из начальной точки, равно сумме путей, ведущих к точкам A и B.

Многим из нас известен этот вывод, потому что точка С имеет только два источника, один — точка А, а другой — точка В. Он может исходить как из точки А, так и из точки Б, поэтому это должно быть аддитивное отношение.

Это, конечно, верно, но я не знаю, есть ли у вас какие-либо идеи из этого процесса. Выше по течению от точки С находятся точка А и точка В, то есть состояние С переносится из состояния А или состояния В. Разве это не алгоритм динамического программирования?

Если мы используем dp для записи ответа каждой позиции, то уравнение перехода состояний можно легко написать:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Мы можем решить проблему, реализовав это уравнение в коде.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for _ in range(n+2)] for _ in range(m+2)]
        
        dp[0][1] = 1
        
        for i in range(1, m+1):
            # 特殊处理第一列，因为第一列只有1种
            dp[i][1] = dp[i-1][1]
            for j in range(2, n+1):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                
        return dp[m][n]

one more solution

Если выше есть только одно решение, то этот вопрос совершенно лишний и слишком простой. Есть другое решение этой проблемы,было бы проще.

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

Разберем задачу, робот должен пройти из левого верхнего угла в правый нижний, карта безупречна и до всех точек можно добраться. из-за роботаНет способа вернуться, то есть определяется расстояние, пройденное роботом в процессе достижения конечной точки. То есть необходимо взять n-1 горизонтальных ребер и m-1 вертикальных ребер.

Определяется общее количество и типы ребер, фактически эта задача может быть преобразована. Мы рассматриваем горизонтальную сторону как белый шар, а вертикальную сторону как черный шар, тогда эта задача фактически может быть преобразована в, у нас есть n-1 белых шаров, m-1 черных шаров, и теперь расположим их в ряд, как всего способов много?

Это комбинаторная математическая задача в начальной школе.Нам нужно выбрать n-1 объектов из общего числа n+m-2 объектов, тогда очевидный ответ:

Однако, хотя мы выражаем это в одной формуле, для решения этого комбинационного числа нам все равно нужно пройти цикл. Превращаем в:

Затем мы можем использовать цикл для ее решения.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        ret = 1
        
        for i in range(1, n):
            ret = ret * (n+m-1-i) // i
        return ret

Короче, чем выше, хотя оба кажутсяАлгоритм, кажется, совсем другой. Но факториал и комбинация каждого числа могут бытьпредварительная обработкаДа, он явно быстрее алгоритма динамического программирования в сценарии частого решения.

конец

Даже если этот вопрос будет закончен, каждый обнаружит, что после того, как LeetCode прошел 50 вопросов, задействовано значительно меньше новых алгоритмов. В конце концов, LeetCode не является платформой для высокоинтенсивных алгоритмов, и ее основное внимание уделяется внедрению алгоритмов. Это также ограничивает его сложность по сравнению с такими платформами, как codeforces и topcoder, которые являются основными конкурентами алгоритмов. Многим людям становится скучно, когда они доходят до 100 вопросов.

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

Перефразируя фразу из фильма в конце:we need to go deeper.

Это все, что касается сегодняшней статьи, мистер Кангуан,пожалуйста следуйте за мной

Категории