Не знаете динамического программирования? 21 вопрос LeetCode поможет вам научиться динамическому программированию!

алгоритм LeetCode
Не знаете динамического программирования? 21 вопрос LeetCode поможет вам научиться динамическому программированию!

"Это 17-й день моего участия в августовском испытании обновлений. Ознакомьтесь с подробностями мероприятия:  Испытание августовского обновления"

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

Примечание:Тема LeetCode 21, связанная с динамическим программированием в этой статье, взята из часто исследуемых тем динамического программирования в CodeTop.Статья длинная, полный текст составляет около 15 000 слов, и вы можете собрать волну~~

动态规划.png

1. Обзор динамического программирования

(1) Основные понятия

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

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

В динамическом программировании есть две важные концепции:

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

Этапы решения задачи динамического программирования:

  1. Определение состояния: Узнайте абстрактное определение подзадачи.
  2. Определите уравнение перехода состояний: выясните рекуррентную связь между состояниями.
  3. Первоначальные состояния и граничные случаи: результат простейшей подпроблемы, который также является состоянием выхода программы.
  4. Возвращаемое значение: для простых задач возвращаемым значением может быть конечное состояние; для сложных задач может потребоваться дополнительная обработка конечного состояния.

посредством следующихпроблема с подъемом по лестницеДавайте взглянем на конкретное применение динамического программирования.

Описание темы: Предположим, вы поднимаетесь по лестнице. Вам нужно n шагов, чтобы добраться до вершины здания. Вы можете подняться на 1 или 2 ступеньки каждый раз. Сколькими способами можно добраться до вершины здания? где n — целое положительное число.

Пример 1:

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

Пример 2:

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

Этот вопрос имеет две ключевые особенности:

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

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

  • Последний шаг - подняться на 1 ступеньку, а впереди n - 1 ступенек, в этом случае имеется f(n - 1) методов;
  • Последний шаг — подняться на 2 ступени, а впереди n - 2 ступени, в этом случае имеется f(n - 2) методов;

f(n) представляет собой сумму двух вышеупомянутых случаев, то есть f(n)=f(n-1)+f(n-2), что является рекуррентным соотношением, используемым в этом вопросе. Давайте посмотрим на это в соответствии с четырьмя шагами динамического программирования:

  1. определение состояния: Инициализировать массив f, f[i] представляет количество методов для подъема на уровень i;
  2. уравнение перехода состояния: f(n)=f(n-1)+f(n-2);
  3. начальное состояние: Для одной ступени существует 1 метод лазания; когда есть две ступени, вы можете подниматься по одной ступени за раз или вы можете подниматься по две ступени за раз, существует 2 метода лазания. То есть f[1] = 1, f[2] = 2;
  4. возвращаемое значение: f[n] , то есть сколько способов лазания существует для n шагов.

Код реализации динамического программирования выглядит следующим образом:

/**
* @param {number} n
* @return {number}
*/
const climbStairs = function(n) {
    // 初始化状态数组
    const f = [];
    // 初始化已知值
    f[1] = 1;
    f[2] = 2;
    // 动态更新每一层楼梯对应的结果
    for(let i = 3;i <= n;i++){
        f[i] = f[i-2] + f[i-1];
    }
    // 返回目标值
    return f[n];
};

(2) Сценарии использования

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

Проблема ветвления была упомянута выше, и ее основная идея заключается в следующем:Разбейте проблему на независимые подзадачи, решите подзадачи одну за другой, а затем объедините ответы подзадач, чтобы получить окончательное решение проблемы.

Идея динамического программирования чем-то похожа на «разделяй и властвуй». Разница в том, что в идее «разделяй и властвуй» каждая подзадача независима: например, при сортировке слиянием порядок подмассивов не влияет друг на друга. Подзадачи, разделенные динамическим программированием, часто взаимозависимы и влияют друг на друга.

Итак, для решения каких задач следует использовать динамическое программирование? Чтобы зафиксировать следующие ключевые характеристики:

  • оптимальное основание, что означает, что оптимальное решение задачи содержит оптимальное решение подзадач — независимо от предыдущего решения, последующее состояние должно быть оптимальным решением, основанным на текущем состоянии (выработанном последним решением). Что касается этого предмета,f(n)а такжеf(n-1),f(n-2)Соотношение между (уравнение перехода состояния) подтверждает это.
  • перекрывающиеся подзадачи, в процессе рекурсии происходит повторное вычисление.
  • нет последействия, Есть два значения отсутствия последействия.Первое значение состоит в том, что при выводе состояния более поздней стадии рассматривается только значение состояния предыдущей стадии, а не то, как состояние получается шаг за шагом. Второе значение заключается в том, что, как только состояние определенного этапа определено, оно не будет затронуто решением следующего этапа. Отсутствие последствий — очень «расслабленное» требование. До тех пор, пока модель задачи динамического программирования, упомянутая выше, удовлетворяется, фактически никакие последствия не будут удовлетворены.

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

2. Проблема пути LeetCode

(1) Различные пути

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

В. Сколько всего существует различных путей?Пример 1:

输入：m = 3, n = 7
输出：28

Пример 2:

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

Пример 3:

输入：m = 7, n = 3
输出：28

Пример 4:

输入：m = 3, n = 3
输出：6

намекать:

  • 1 <= m, n <= 100
  • Данные вопроса гарантируют, что ответ меньше или равен2 * 10

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

Количество путей в каждой сетке связано с количеством путей на ее верхней и левой сторонах, и можно вывести рекурсивное уравнение:

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

Сначала инициализируйте двумерный массив m * n.Все значения узлов массива изначально равны 0. Поскольку самая верхняя строка и самый левый столбец являются границами, может быть только один способ перемещения, поэтому начальное значение равно 1 . Тогда его можно решить по рекуррентному уравнению.

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))

    for(let i = 0; i < m; i++){
        dp[i][0] = 1
    }
    for(let j = 0; j < n; j++){
        dp[0][j] = 1
    }

    for(let i = 1; i < m; i++){ 
        for(let j = 1; j < n; j++){
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
};

Анализ сложности:

  • Временная сложность: O(mn), где m и n — длина и ширина сетки соответственно, нам нужны два слоя обхода, поэтому пространственная сложность равна O(mn).
  • Сложность пространства: O(mn), где m и n — длина и ширина сетки соответственно, нам нужен двумерный массив m * n для хранения всех состояний, поэтому требуемая сложность пространства равна O(mn).

(2) Различные пути II

Робот находится вm x nВерхний левый угол сетки (начальная точка отмечена как «Начало» на изображении ниже).

Робот может двигаться вниз или вправо только на один шаг за раз. Робот пытается достичь нижнего правого угла сетки (помеченного «Готово» на изображении ниже).

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

Препятствия и пустые позиции в сетке соответственно1а также0Представлять.

Пример 1:

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

Пример 2:

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

намекать:

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j]для0или1

Этот вопрос и 62 вопроса с разными путями — одна и та же идея:динамическое программирование.

Отличие в том, что в этой теме есть препятствия, поэтому при прохождении нужно обратить внимание на следующие два момента:

  • При установке начальных значений для элементов первой строки и первого столбца, если значение сетки равно 1, то есть есть препятствие, оно остановится сразу, и нет необходимости продолжать движение вперед, т.к. предыдущий может быть проходящим;
  • При подсчете количества путей в каждой сетке, если элемент сетки присутствует, он будет пропущен без расчета.

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

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    if(!obstacleGrid.length || obstacleGrid[0][0] === 1){
        return 0
    }

    const m = obstacleGrid.length, n = obstacleGrid[0].length
    const dp = new Array(m).fill(0).map(() =>  new Array(n).fill(0))

    for (let i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
        dp[i][0] = 1;
    }
    for (let j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
        dp[0][j] = 1;
    }
    
    for(let i = 1; i < m; i++){ 
        for(let j = 1; j < n; j++){
            if(obstacleGrid[i][j] === 0){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
    }
    return dp[m - 1][n - 1]
};

Анализ сложности:

  • Временная сложность: O(mn), где m и n — длина и ширина сетки соответственно, нам нужны два слоя обхода, поэтому пространственная сложность равна O(mn).
  • Сложность пространства: O(mn), где m и n — длина и ширина сетки соответственно, нам нужен двумерный массив m * n для хранения всех состояний, поэтому требуемая сложность пространства равна O(mn).

(3) Минимальный путь и

Дан массив, содержащий неотрицательные целые числаm x nсеткаgrid, найдите путь из левого верхнего угла в правый нижний угол такой, что сумма чисел на пути будет наименьшей.

проиллюстрировать:Вы можете двигаться вниз или вправо только на один шаг за раз.  

Пример 1:

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

Пример 2:

输入：grid = [[1,2,3],[4,5,6]]
输出：12

намекать:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

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

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

grid[i][0] += grid[i - 1][0]

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

grid[0][j] += grid[0][j - 1]

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

grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];

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

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    let m = grid.length, n = grid[0].length

    for(let i = 1; i < m; i++){
        grid[i][0] += grid[i - 1][0]
    }
    for(let j = 1; j < n; j++){
        grid[0][j] += grid[0][j - 1]
    }

    for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
        }
    }
    return grid[m - 1][n - 1]
}

Анализ сложности:

  • Временная сложность: O(mn), где m и n — количество строк и столбцов сетки соответственно. Всю сетку нужно пройти один раз, и вычислить значение каждого элемента сетки.
  • Сложность пространства: O(1), здесь мы работаем на основе исходного массива, а требуемое дополнительное пространство является постоянным.

(4) Треугольная сумма минимального пути

данный треугольникtriangle, найти минимальную сумму пути сверху вниз.

Каждый шаг может перемещаться только к соседним узлам в следующей строке.

соседние узлызначит здесьиндекса такжеИндекс предыдущего узлатакой же или равныйиндекс предыдущего узла + 1из двух узлов. То есть, если вы находитесь в нижнем индексе текущей строкиi, то следующий шаг может перейти к индексу следующей строкиiилиi + 1.  

Пример 1:

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

Пример 2:

输入：triangle = [[-10]]
输出：-10

намекать:

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -104 <= triangle[i][j] <= 104

  Передовой:

  • вы можете просто использоватьO(n)дополнительное место (nна общее количество строк в треугольнике) для решения этой задачи?

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

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

Здесь также необходимо решить проблему двух границ.Для первого столбца элементов он может спуститься только из элементов выше, поэтому его уравнение перехода состояния:

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

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

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

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

triangle[i][j] += Math.min(triangle[i - 1][j], triangle[i - 1][j - 1])

Наконец, нам нужно только вернуть минимальное значение элементов в последней строке.Здесь мы используем оператор ...spread с методом min в Math, чтобы найти минимальное значение последней строки.

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    const n = triangle.length

    for(let i = 1; i < n; i++){
        for(let j = 0; j <= i; j++){
            if(j === 0){
                triangle[i][j] += triangle[i - 1][j]
            }else if(j === i){
                triangle[i][j] += triangle[i - 1][j - 1]
            }else{
                triangle[i][j] += Math.min(triangle[i - 1][j], triangle[i - 1][j - 1])
            }
        }
    }

    return Math.min(...triangle[n - 1])
};

Анализ сложности:

  • Временная сложность: O(n2), где n — количество строк треугольника.
  • Пространственная сложность: O(1). Здесь мы работаем на основе исходного массива, поэтому требуемое дополнительное пространство является постоянным.

3. LeetCode покупает и продает акции

(1) Лучшее время для покупки и продажи акций

Учитывая массив, его первыйiэлемент - это номер данной акцииiдневная цена. Если вам разрешено совершить не более одной сделки (т. е. купить и продать акции один раз), разработайте алгоритм для расчета максимальной прибыли, которую вы можете получить. Примечание. Вы не можете продать акцию до ее покупки.

Пример 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

Пример 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

(1) Прямой обход

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

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

(2) динамическое программирование

Для этой задачи мы можем использоватьдинамическое программированиерешать. Здесь нам нужно только сделать одну покупку и продать. К моменту финальной транзакции может быть три состояния:

  • dp[0]: никогда не покупал
  • dp[1]:: В итоге я купил только один, но не продал
  • dp[2]:: продал только один в конце, и продал

Поскольку в первом состоянии никакая операция не выполняется, запись не требуется. Затем делаем переходы в последние два состояния:

  • dp[1] = Math.max(dp[1], -prices[i]): предыдущий день также был в состоянии b1 или операции не было, а покупка сегодня становится состоянием b1;
  • dp[2] = Math.max(dp[2], dp[1] + prices[i]): предыдущий день также был в состоянии s1 или в состоянии b1, а сегодняшняя продажа становится состоянием s1;

(1) Прямой обход

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let max = 0
    let min = prices[0]

    prices.forEach( item => {
        if(item < min) min = item
        if(item - min > max) max = item - min
    })
    return max
};

Анализ сложности:

  • временная сложность:O(n), где n — длина массива, нам нужно перебрать массив
  • Сложность пространства:O(1), здесь требуется только постоянное пространство для хранения минимального значения min и максимального значения результата max

(2) Динамическое программирование

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let len = prices.length;
    const dp = [0, -prices[0], 0]
    
    for (let i = 1; i < len; i++) {
        dp[1] = Math.max(dp[1], -prices[i])
        dp[2] = Math.max(dp[2], dp[1] + prices[i])
    }
    return dp[2];
}

Анализ сложности:

  • временная сложность: O(n), где n — длина массива цен.
  • космическая сложность: O (1).

(2) Лучшее время для покупки и продажи акций II

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

Пример 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

Пример 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

Пример 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

намекать:

  • 1 <= prices.length <= 3 * 10
  • 0 <= prices[i] <= 10

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

1) dp[i][0] означает: В i-й день нет запасов в наличии и пока максимальная прибыль (i-й день). Если в день i в наличии нет запасов, есть две возможности:

  • Вчера не владел акциями: dp[i-1][0]
  • Купили акции вчера, продали сегодня: dp[i-1][1] + цены[i]
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])

2) dp[i][1] означает: запас в наличии на i-й день и максимальную прибыль на данный момент (i-й день). В день i есть акции на руках, есть две возможности:

  • Вчера тоже были акции: dp[i-1][1]
  • Вчера продано, сегодня куплено: dp[i-1][0] - цены[i]
  • dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

Конечная цель состоит в том, чтобы найти:dp[prices.length-1][0]а такжеdp[prices.length-1][1]Большее из , первое должно быть >= второе, найтиdp[prices.length-1][0]Вот и все.

Для начала:

  • не покупал в день 0: dp[0][0] = 0
  • Куплено в день 0: dp[0][1] = -prices[0]
/**
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
  const len = prices.length;
  if (len < 2) {
    return 0;
  };
  const dp = new Array(len);
  dp[0] = [0, -prices[0]];
  for (let i = 1; i < len; i++) {
    dp[i] = new Array(2);
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 没有股票
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); // 有股票
  }
  return dp[len - 1][0];
}

Анализ сложности:

  • временная сложность:O(n), где n — длина массива. Всего существует 2n состояний, а временная сложность каждого перехода между состояниями равна O(1), поэтому временная сложность равна O(2n)=O(n).
  • космическая сложность: O(n), нам нужно освободить O(n) пространства для хранения всех состояний в динамическом программировании.

(3) Лучшее время для покупки и продажи акций III

Дан массив, i-й элемент которого — цена данной акции в i-й день. Разработайте алгоритм для расчета максимальной прибыли, которую вы можете получить. Вы можете выполнить додва удараторговля. Примечание. Вы не можете участвовать в нескольких сделках одновременно (вы должны продать предыдущие акции, прежде чем покупать снова).

Пример 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

Пример 2:

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

Пример 3:

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

Пример 4:

输入：prices = [1]
输出：0

намекать:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 105

Для этой задачи мы можем использоватьдинамическое программированиерешать. В «Лучшее время для покупки и продажи акций» мы можем совершить только одну покупку и продажу. В этом вопросе мы можем покупать и продавать не более двух раз, в конце сделки может быть пять состояний:

  • dp[0]: никогда не покупал
  • dp[1]: Я купил только одну сумму в конце, но не продал ее
  • dp[2]: В конце была продана только одна продажа, и она была продана
  • dp[3]: В итоге купил два, а продал только один
  • dp[4]: В итоге купил два и продал оба

Поскольку в первом состоянии никакая операция не выполняется, запись не требуется. Затем делаем переходы в последние четыре состояния:

  • dp[1] = Math.max(dp[1], -prices[i]): предыдущий день также был в состоянии b1 или операции не было, а покупка сегодня становится состоянием b1;
  • dp[2] = Math.max(dp[2], dp[1] + prices[i]): предыдущий день также был в состоянии s1 или в состоянии b1, а сегодняшняя продажа становится состоянием s1;
  • dp[3] = Math.max(dp[3], dp[2] - prices[i]): предыдущий день также был в состоянии b2 или s1, а покупка суммы сегодня становится состоянием b2;
  • dp[4] = Math.max(dp[4], dp[3] + prices[i]): Предыдущий день также был в состоянии s2 или в состоянии b2, а сегодня возникла сумма, которая стала состоянием s2.
/**
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
    let len = prices.length;
    const dp = [0, -prices[0], -prices[0], 0, 0]
    
    for (let i = 1; i < len; i++) {
        dp[1] = Math.max(dp[1], -prices[i])
        dp[2] = Math.max(dp[2], dp[1] + prices[i])
        dp[3] = Math.max(dp[3], dp[2] - prices[i])
        dp[4] = Math.max(dp[4], dp[3] + prices[i])
    }
    return dp[4];
};

Анализ сложности:

  • временная сложность: O(n), где n — длина массива цен.
  • космическая сложность: О(1).

(4) Лучшее время для покупки и продажи акций IV

Для заданного целочисленного массива Prices его i-й элемент price[i] является ценой данной акции в i-й день. Разработайте алгоритм для расчета максимальной прибыли, которую вы можете получить. Вы можете совершить до k транзакций. Примечание. Вы не можете участвовать в нескольких сделках одновременно (вы должны продать предыдущие акции, прежде чем покупать снова).

Пример 1:

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

Пример 2:

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

намекать:

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

В теме "Лучшее время для покупки и продажи акций" мы можем совершить только одну покупку и продажу, а в теме 123 "Лучшее время для покупки и продажи акций III" мы можем совершить две операции покупки и продажи. В этой задаче мы можем выполнить k операций покупки и продажи. Здесь мы также можем использоватьдинамическое программированиеотвечать.

каждый раз, когда мы можем только сделать[1, k]Одна из транзакций или нет транзакции, поэтому может быть 2k+1 состояний:

  • Никаких действий, никогда не покупал
  • dp[0]: только одна покупка была куплена в конце, но не продана
  • dp[1]: в конце была продана только одна продажа, и она была продана
  • dp[2]: Я купил два в конце и продал только один
  • dp[3]: Я купил два в конце, и оба были проданы
  • dp[4]: Я купил три в конце и продал только два
  • ······

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

  • Без транзакций, деньги без изменений
  • провести[1, k]сделки
    • покупка, наличные = цена акции дня
    • Продать за наличные += курс акций дня
/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(k, prices) {
    const dp = new Int16Array(k * 2).fill(-prices[0])
    
    for (let i = 0; i < prices.length; i++) {
        for (let j = 0; j < dp.length; j++) 
            {
                dp[j] = Math.max(dp[j], (dp[j - 1] || 0) + (j & 1 ? prices[i] : -prices[i]))
            }
    }
    return Math.max(0, ...dp) 
};

Анализ сложности:

  • временная сложность: O(n * min(n, k)), где n — длина массива цен, т.е. время, необходимое для динамического программирования с двойным циклом.
  • космическая сложность: O(мин(n,k)).

4. Проблема ограбления LeetCode

(1) ограбление

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

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

Пример 1:

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

Пример 2:

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

намекать:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400

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

  • Если вы украли n-ю комнату, то вы не можете украсть n-1-ю комнату, тогда общая сумма равна сумме наибольшей суммы, которую можно украсть из первых n-2 комнат;
  • Если k-я комната не украдена, общая сумма, которую можно украсть, равна наибольшей общей сумме первых k - 1 комнат.

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

Мы можем использовать dp[i] для представления максимальной общей суммы, которую можно украсть из первых i домов, тогда мы получим следующее уравнение перехода состояний:

dp[i]=max(dp[i−2]+nums[i],dp[i−1])

Граничные условия:

  • dp[0] = nums[0] : если есть только один дом, украсть этот дом
  • dp[1] = max(nums[0], nums[1]): Есть только два дома, выберите дом с большей суммой для кражи

Окончательный ответ: dp[n−1], где n — длина массива.

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const len = nums.length
    if(!len){
        return 0
    }

    const dp = new Array(len + 1)
    dp[0] = 0
    dp[1] = nums[0]

    for(let i = 2; i <= len; i++){
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
    }
    return dp[len];
};

Анализ сложности:

  • Временная сложность: O(n), где n — длина массива. Вам нужно только один раз перебрать массив.
  • Пространственная сложность: O(1). Используйте массив для хранения только наибольшего общего количества первых двух домов, а не результата всего массива, поэтому сложность пространства равна O (1).

(2) Ограбление II

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

Учитывая массив неотрицательных целых чисел, представляющих количество, хранящееся в каждом доме, рассчитайте свойбез срабатывания сигнализации, максимальная сумма, которую можно украсть.  Пример 1:

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

Пример 2:

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

Пример 3:

输入：nums = [0]
输出：0

намекать:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

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

  • не кради первым
  • не кради последний

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

Максимальное значение текущего узла — это текущий узел и максимальное значение предыдущего второго узла и значение предыдущего узла, которые могут быть обернуты вокруг кода уравнения передачи статуса:

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])

Код:

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const len = nums.length
    let res1 = 0, res2 = 0
    if(len === 0) return 0
    if(len === 1) return nums[0]

    const dp = new Array(len)
    
    // 不偷第一家
    dp[0] = 0
    dp[1] = nums[1]
    for(let i = 2; i <= len - 1; i++){
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    res1 = dp[len - 1]

    // 不偷最后一家
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])
    for(let i = 2; i <= len - 2; i++){
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    res2 = dp[len - 2]
    return Math.max(res1, res2)
};

Анализ сложности:

  • Временная сложность: O(n), где n — длина массива, нам нужно пройти по массиву дважды;
  • Сложность пространства: O(n), где n — длина массива, нам нужно инициализировать массив длины n, чтобы сохранить состояние текущего узла.

(3) Ограбление III

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

Подсчитайте максимальную сумму, которую вор может украсть за одну ночь, не сработав сигнализации.

Пример 1:

输入: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \ 
     3   1
输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

Пример 2:

输入: [3,4,5,1,3,null,1]
     3
    / \
   4   5
  / \   \ 
 1   3   1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

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

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

  • Когда узел выбран, его левый и правый дочерние элементы не могут быть выбраны, поэтому максимальное значение равно: node.val + left[1] + right[1];
  • Когда узел не выбран, его левый и правый дочерние элементы могут быть выбраны или нет, поэтому максимальное значение равно: Math.max(left[0], left[1]) + Math.max(right[0], right[ 1]);

Наконец, верните максимальное значение в левом и правом поддеревьях.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    const dfs = (node) => {
        if (node === null) {
            return [0, 0];
        }
        const left = dfs(node.left);
        const right = dfs(node.right);
      
        const select = node.val + left[1] + right[1];
        const notSelect = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return [select, notSelect];
    }
    const res = dfs(root)
    return Math.max(res[0], res[1])
};

Анализ сложности:

  • Временная сложность: O(n), выполняется обратный обход бинарного дерева, поэтому временная сложность равна O(n);
  • Сложность пространства: O(n), стоимость использования рекурсивного пространства стека составляет O(n).

5. Проблема палиндрома LeetCode

(1) Палиндромная подстрока

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

Пример 1:

输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

Пример 2:

输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

Совет: длина входной строки не должна превышать 1000 .

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

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

Анализ сложности:

  • Временная сложность O(n2), требующая двух уровней обхода.
  • Пространственная сложность O (1)
/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let count = s.length
    let len = s.length
    for(let i = 0; i < len; i++){
        for(let j = i + 1; j < len; j++){
            let temp = s.substr(i, j-i+1)
            if(isSub(temp)){
                count++
            }
        }
    }
    return count
};
const isSub = str => {
        let a = 0
        let b = str.length - 1
        while(a <= b){
            if(str[a] !== str[b]){
                return false
            }
            a++
            b--
        }
        return true
    }

(2) Самая длинная подстрока палиндрома

Для строки s найти самую длинную подстроку палиндрома в s. Вы можете предположить, что s имеет максимальную длину 1000.

Пример 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

Пример 2:

输入: "cbbd"
输出: "bb"

Вот два подхода к ответу на этот вопрос:

(1) Метод 1: метод расширения центра

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

  • Выберите центр симметрии (центр строки нечетной длины — это середина двух символов, а центр строки четной длины — средний символ).
  • Большие длины подстрок палиндрома двух комбинаций, полученные после сравнения и расширения
  • Сравните предыдущую длину, чтобы определить, следует ли обновлять начальную позицию
  • После обхода по начальной позиции перехватить самую длинную подстроку палиндрома

Код:

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if(s == null || s.length <1){
        return ''
    }
    let start = 0
    let end = 0
    // 定义中心扩展的方法
    const fn = (s,left,right) => {
        while(left >=0 && right< s.length && s[left] === s[right]){
            left--
            right++
        }
        return right - left -1
    }
    // 遍历字符串
    for(let i = 0; i<s.length; i++){
        const len1 = fn(s, i, i)
        const len2 = fn(s, i, i+1)
        const len = Math.max(len1, len2)
        // 判断起始位置是否更新
        if(len > end - start){
            start = i- Math.floor((len-1)/2)
            end = i+ Math.floor(len/2)
        }
    }
    return s.substring(start, end+1)
};

Анализ сложности:

  • временная сложность: O(n2), временная сложность перечисления «центральной позиции» равна O(n), а временная сложность получения «палиндромной подстроки» из «центральной позиции» равна O(n), поэтому временная сложность равна О(п2).
  • космическая сложность: O(1), здесь используются только две постоянные временные переменные start и end, поэтому пространственная сложность равна O(1).

(2) Метод 2: динамическое программирование

Основная идея решения такого рода задач состоит в двух словахпродлевать, конкретно

  • Если строка является палиндромом, то слева и справа от нее добавить один и тот же символ, тогда она все равно должна быть палиндромом
  • Если вы добавите какие-либо символы к обоим концам строки, не являющейся палиндромом, или добавите разные символы слева и справа от палиндрома, результат не должен быть палиндромом.

Фактически приведенный выше анализ установилбольшая проблемаа такженебольшая проблемаСвязь между ними, потому что мы можем создать модель динамического программирования. Может ли dp [i] [j] указать, может ли s-палиндром быть сформирован от i до j (включая i и j), уравнение перехода состояния, описанное выше, за исключением того, что код может быть преобразован к:

if (s[i] === s[j] && dp[i + 1][j - 1]) {
  dp[i][j] = true;
}

в:

  • s[i] === s[j]: указывает, что текущий центр может продолжать расширяться, что может увеличить длину палиндрома.
  • dp[i+1][j-1]: true, что указывает на то, что подстрока s[i+1][j-1] строки s[i,j] также является палиндромом, где i проходится от максимального значения, j проходится от минимального значения

Подводя итог, конкретные шаги реализации с использованием динамического программирования следующие:

  • Чтобы определить, является ли dp[i][j] палиндромом, достаточно, чтобы dp[i+1][j-1] был палиндромом и s[i] === s[j].
  • Палиндромы длины 0 или 1 требуют специальной обработки, т.е. j-i
  • Поскольку знание dp[i] требует сначала знания dp[i+1], мне нужно пройти от большого к меньшему
  • Потому что, зная dp[j], нужно сначала знать dp[j-1], поэтому j нужно пройти от малого к большому.

Код:

 /**
 * @param {string} s
 * @return {string}
 */
// 扩展中心
var longestPalindrome = function(s) {
   let res = '';
    let n = s.length;
    let dp = Array.from(new Array(n), () => new Array().fill(0));
    
    for(let i = n-1; i >=0; i--) {
        for(let j = i; j < n; j++) {
            dp[i][j] = s[i] === s[j] && ( j - i < 2 || dp[i+1][j-1])
            if(dp[i][j] && j - i + 1 > res.length) {
                res = s.substr(i,j - i + 1);
            }
        }
    }
    return res;
}

Анализ сложности:

  • временная сложность: O(n2), где n — длина строки. Общее количество состояний для динамического программирования равно O(n2), и для каждого состояния время, необходимое для перехода, равно O(1).
  • космическая сложность: O(n2) — пространство, необходимое для хранения состояния динамического программирования.

(3) Самая длинная подпоследовательность палиндрома

задана строкаs, найти самую длинную палиндромную подпоследовательность и вернуть длину последовательности. Можно предположитьsМаксимальная длина1000.  

Пример 1:

输入: "bbbab"
输出: 4
一个可能的最长回文子序列为 "bbbb"。

Пример 2:

输入: "cbbd"
输出: 2
一个可能的最长回文子序列为 "bb"。

намекать:

  • 1 <= s.length <= 1000
  • sСодержит только строчные английские буквы

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

Здесь мы пытаемся использовать динамическое программирование для ответа, инициализируем двумерный массив dp, чтобы сохранить длину подстроки, dp[i][j] представляет подстроку, состоящую из i-го символа до j-го символа в s , самая длинная Длина палиндромной последовательности.

Ниже самое главное найти уравнение перехода состояния:

  • Если i-й и j-й символы строки s совпадают:f[i][j] = f[i + 1][j - 1] + 2
  • Если i-й и j-й символы строки s не совпадают:f[i][j] = max(f[i + 1][j], f[i][j - 1])

Здесь вам нужно обратить внимание на порядок обхода: i проходится от последнего символа, а j проходится в обратном направлении от i+1, чтобы обеспечить расчет каждой подзадачи. Наконец просто вернутьсяdp[0][len-1]Вот и все.

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function(s) {
    let len = s.length;
    
    let dp = new Array(len)
    for (let i = 0; i < len; i++) {
        dp[i] = new Array(len).fill(0);
    }
    
    for (let i = len - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (let j = i+1; j < len; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
            }
        }
    }
    return dp[0][len-1];
};

Анализ сложности:

  • Временная сложность: O(n2), где n — длина строки, нам нужен двухслойный обход;
  • Пространственная сложность: O(n2), где n — длина строки, нам нужно инициализировать двумерный массив.

6. Проблема подпоследовательности LeetCode

(1) Максимальная сумма подзаказа

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

Пример:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

Передовой:Если вы реализовали сложность O(n), попробуйте более тонкое решение по принципу «разделяй и властвуй».

Решатель динамического программирования:Обычно мы обходим подстроку или подпоследовательность тремя способами.

  • Все подпоследовательности, начинающиеся с определенного узла: такие как [a], [a, b], [a, b, c]... Затем проходят [b] [b, c из подпоследовательности, начинающейся с b].
  • В соответствии с длиной подпоследовательности в качестве эталона, например, сначала пройти подпоследовательность, длина которой равна 1, затем пройти подпоследовательность, длина которой равна 2, и так далее.
  • Основываясь на конечном узле подпоследовательности, сначала пройдите все подпоследовательности, заканчивающиеся определенным узлом, поскольку каждый узел может быть конечным узлом подпоследовательности, поэтому необходимо пройти всю последовательность, например: конец на b Все подпоследовательности точек: [a , b] [b] , все подпоследовательности, оканчивающиеся на c: [a, b, c] [b, c] [c].

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

Код:

var maxSubArray = function(nums) {
    let sum = 0, res = nums[0]
    for(let num of nums){
        sum > 0 ? sum += num : sum = num
        res = Math.max(sum, res)
    }
    return res
};

Анализ сложности:

  • Временная сложность: O(n), где n — длина массива nums, и вам нужно пройти по массиву только один раз, чтобы получить ответ.
  • Сложность пространства: O(1), для хранения нескольких переменных требуется только постоянное пространство.

(2) Самая длинная возрастающая подпоследовательность

Дан массив целых чисел nums , найти в нем длину самой длинной строго возрастающей подпоследовательности.

Подпоследовательность — это последовательность, полученная из массива, которая удаляет (или не удаляет) элементы из массива без изменения порядка оставшихся элементов. Например, [3,6,2,7] является подпоследовательностью массива [0,3,1,6,2,2,7].

Пример 1:

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

Пример 2:

输入：nums = [0,1,0,3,2,3]
输出：4

Пример 3:

输入：nums = [7,7,7,7,7,7,7]
输出：1

намекать:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

Передовой:

  • Можете ли вы разработать решение с временной сложностью O(n2)?
  • Можете ли вы уменьшить временную сложность алгоритма до O(n log(n))?

Когда дело доходит до проблемы подпоследовательностей, самое простое, что можно придумать, это динамическое программирование. Сначала инициализируйте массив dp, чтобы сохранить оптимальное решение каждой подзадачи, dp[i] представляет самую длинную непрерывную подпоследовательность из первых n элементов массива и, наконец, верните самую длинную последовательность из всех подпоследовательностей.

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    const n = nums.length
    if(!n){
        return 0
    }

    let dp = new Array(n).fill(1)
    for(let i = 1; i < n; i++){
        for(let j = 0; j < i; j++){
            if(nums[i] > nums[j]){
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp)
};

Анализ сложности:

  • временная сложность: O(n), где n — длина массива nums. Количество состояний в динамическом программировании равно n. При вычислении состояния dp[i] требуется время O(n) для прохождения всех состояний dp[0…i−1], поэтому общая временная сложность составляет O(n ).
  • космическая сложность: O(n), требует дополнительного использования массива dp длины n.

(3) Подмассив с наибольшим произведением

дает вам массив целых чиселnums, найдите непрерывный подмассив с наибольшим произведением в массиве (подмассив содержит хотя бы одно число) и верните соответствующий продукт подмассива.  

Пример 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

Пример 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

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

Нам нужно только постоянно обновлять максимальное значение при обходе массива, В этом процессе нам нужно поддерживать два значения:

  • max, текущее максимальное значение, сравнить текущее значение с произведением текущего значения и предыдущего максимального значения и сохранить максимальное значение
  • min, текущее минимальное значение, сравнить текущее значение с произведением текущего значения и предыдущего минимального значения и сохранить минимальное значение

Мы просим здесь максимальное значение, так зачем сохранять минимальное значение? Это связано с тем, что в массиве могут быть отрицательные числа.Когда текущее значение отрицательное, умножение на предыдущее значение приведет к тому, что максимальное и минимальное значения будут заменены местами, поэтому нам нужно сохранить максимальное значение и минимальное значение. Затем продолжайте использовать текущее максимальное значение для сохранения в качестве результата и, наконец, верните результат.

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let res = -Infinity, max = 1, min = 1;

    for(let i = 0; i < nums.length; i++){
        if(nums[i] < 0){
            let temp = max
            max = min
            min = temp
        }
        max = Math.max(nums[i], nums[i] * max)
        min = Math.min(nums[i], nums[i] * min)

        res = Math.max(res, max)
    }
    return res
};

Анализ сложности:

  • Временная сложность: O(n), нам нужно пройти массив один раз, поэтому временная сложность равна O(n);
  • Сложность пространства: O(1), дополнительное пространство, которое нам здесь нужно, является постоянным, поэтому сложность пространства равна O(1).

(4) Самый длинный повторяющийся подмассив

к двум целочисленным массивамAа такжеB, который возвращает длину самого длинного подмассива, общего для двух массивов.  

Пример:

输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。

намекать:

  • 1 <= len(A), len(B) <= 1000
  • 0 <= A[i], B[i] < 100

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

Здесь мы инициализируем массив dp для сохранения текущего максимального непрерывного значения, dp[i][j] представляет длину самого длинного общего подмассива, состоящего из первых i элементов массива A и первых j элементов массива B.

При переборе массива:

  • Если значения двух текущих элементов равны, то есть A[i] === B[j], это означает, что текущий элемент может образовывать общий подмассив, поэтому к длине самого длинного общего подмассива прибавьте единицу подмассив предыдущего элемента, уравнение перехода состояния в это время: dp[i][j] = dp[i - 1][j - 1] + 1;
  • Если текущие значения двух элементов не равны, значение dp в это время сохраняется как 0 (инициализируется равным 0).

В процессе обхода постоянно обновляется максимальное значение самой длинной общей подпоследовательности.

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
var findLength = function(A, B) {
    const m = A.length, n = B.length;

    let dp = new Array(m + 1)
    for (let i = 0; i <= m; i++) { 
        dp[i] = new Array(n + 1).fill(0);
    }

    let res = 0

    for(let i = 1; i <= m; i++){
        for(let j = 1; j <= n; j++){
            if(A[i - 1] === B[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1
            }
            res = Math.max(dp[i][j], res)
        }
    }
    return res
};

Анализ сложности:

  • Временная сложность: O(mn), где m и n — длины двух массивов A и B соответственно.Здесь нам нужно пройти два массива в двух слоях.
  • Пространственная сложность: O(mn), где m и n — длины двух массивов A и B соответственно.Нам нужно инициализировать двумерный массив dp для хранения длины текущего самого длинного общего подмассива.

7. Другие проблемы с LeetCode

(1) Получение дождевой воды

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

Пример 1:

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

Пример 2:

输入：height = [4,2,0,3,2,5]
输出：9

намекать:

  • n == height.length
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105

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

  • Если длина более короткого столбца больше, чем длина текущего столбца, то глубина дождя равна более короткому столбцу минус длина текущего столбца;
  • Если длина более короткого столбца меньше или равна текущему столбцу, глубина дождя равна 0.

Для нижнего индекса i максимальная высота, на которую может подняться вода после дождя, равна минимальному значению максимальных высот по обе стороны от нижнего индекса i, а количество дождевой воды, которое может быть получено на нижнем индексе i, равно максимальной высоте, на которую вода в нижнем индексе i может достигать минус высоты [i].

Самый прямой подход состоит в том, чтобы сканировать слева и справа для каждого элемента в массиве высоты и записывать максимальные высоты слева и справа, а затем вычислять количество дождевой воды, которое может быть получено в каждой позиции нижнего индекса. Используя динамическое программирование, максимальная высота с обеих сторон каждой позиции может быть предварительно обработана за время O(n).

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let len = height.length, sum = 0
    for(let i = 0; i < len - 1; i++){
        // 计算当前柱子左侧的最大值
        let left = 0
        for(let j = i - 1; j >= 0; j--){
            left = Math.max(height[j], left)
        }
        // 计算当前柱子右侧的最大值
        let right = 0
        for(let j = i + 1; j < len; j++){
            right = Math.max(height[j],right)
        }
        // 计算当前柱子能接的雨水量
        if(min > height[i]){
            sum += Math.min(left, right) - height[i]
        }
    }
    return sum
};

Анализ сложности:

  • Временная сложность: O(n), где n — длина высоты массива. Необходимо дважды пройти массив высот;
  • Пространственная сложность: O(1).

(2) Подъем по лестнице

Предположим, вы поднимаетесь по лестнице. нужноnшаги, чтобы достичь вершины. Вы можете подняться на 1 или 2 ступеньки каждый раз. Сколькими способами можно добраться до вершины здания?

Уведомление:даноnявляется положительным целым числом.

Пример 1:

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

Пример 2:

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

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

  • Первый шаг: 1 способ
  • Второй шаг: 2 метода
  • n-й шаг: подняться на один шаг с n-1-го шага или на 2 шага с n-2-го шага

Таким образом, можно вывести рекурсивную формулу: f(n) = f(n−1) + f(n−2) Таким образом, мы можем завершить вычисление рекурсией.

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

Обычная рекурсия:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const dp = []
    dp[0] = 1
    dp[1] = 1
    for(let i = 2; i <= n; i ++){
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
};

Рекурсия памяти:

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let a = 1, b = 1, res = 1;
    for (let i = 1; i < n; i++) {
        a = b
        b = res
        res = a + b
    }
    return res
};

Обычный анализ сложности рекурсии:

  • Временная сложность: O(n2), глубина дерева рекурсии равна n, поэтому временная сложность равна O(n2);
  • Пространственная сложность: O(n), здесь необходимо инициализировать массив для хранения количества методов для каждого шага, имеется n чисел, поэтому пространственная сложность равна O(n);

Анализ сложности рекурсии памяти:

  • Временная сложность: O(n), ее нужно выполнить n раз, поэтому временная сложность равна O(n);
  • Сложность пространства: O(1), здесь в качестве вспомогательного пространства используются только постоянные переменные, поэтому сложность пространства O(1);

(3) Самый большой квадрат

в'0'а также'1'В двумерной матрице, состоящей из, найти только'1', и возвращает его площадь.  

Пример 1:

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

Пример 2:

输入：matrix = [["0","1"],["1","0"]]
输出：1

Пример 3:

输入：matrix = [["0"]]
输出：0

намекать:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j]для'0'или'1'

Для решения этой проблемы можно использовать динамическое программирование.Здесь нам нужно инициализировать массив dp.dp[i][i] представляет максимальную длину стороны квадрата с (i, j) в качестве нижнего правого угла и содержит только 1. . Нам нужно только пройти по этой двумерной матрице, вычислить значение каждого dp, выбрать максимальное значение, то есть максимальную длину стороны квадрата, и, наконец, вернуть площадь квадрата.

Существуют следующие правила расчета каждого значения dp:

  • Если текущее значение равно 0, то точка не существует в квадрате, напрямую присвойте 0 dp[i][j];
  • Если текущее значение равно 1, значение dp[i][j] определяется минимальным значением его верхнего, левого и верхнего левого трех значений, поэтому его уравнение перехода состояния:
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

Кроме того, нам также необходимо рассмотреть крайний левый столбец и верхнюю строку двумерной матрицы.Если значение равно 1, непосредственно присвойте dp[i][j] значение 1.

Код:

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    const m = matrix.length, n = matrix[0].length
    let res = 0
    if(!matrix || m === 0 || n === 0){
        return 0
    }

    let dp = new Array(m)
    for(let i = 0; i < m; i++){
        dp[i] = new Array(n).fill(0)
    }

    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(matrix[i][j] === '1'){
                if(i === 0 || j === 0){
                    dp[i][j] = 1
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                }
                res = Math.max(dp[i][j], res)
            }
        }
    }
    return res * res
};

Анализ сложности:

  • Временная сложность: O(mn), где m и n — количество строк и столбцов двумерной матрицы. Нам нужно перебрать каждый элемент в 2D-матрице, чтобы вычислить значение dp.
  • Пространственная сложность: O(mn), где m и n — количество строк и столбцов двумерной матрицы. Мы создаем массив dp того же размера, что и исходная матрица, чтобы хранить максимальную длину стороны текущего квадрата.

Рекомендуемые статьи по теме:

Категории