[Минималистское динамическое программирование. День четвертый — поймать дождь]

Java

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

425.jpg

Цель этой статьи — записать некоторые обучающие вопросы о dp. Если вы не знакомы с динамическим программированием, перейдите к этой статье.

----

Как я объяснил динамическое программирование своей 5-летней племяннице?

----

Путь к чистке вопросов — долгий путь.

Какие вопросы вы можете решить с помощью динамического программирования?

1. Считать

  • Сколько способов попасть в правый нижний угол
  • Сколькими способами можно выбрать k чисел да и сложить

2. Найдите максимальное и минимальное значения

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

3. Ищите существования

  • В игре со сбором камней обязательно ли выиграет тот, кто сделает первый ход?
  • Можно ли выбрать k чисел так, чтобы сумма была суммой

Тема 1

leetcode 42. Поймай дождь

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

421.jpg

Ввод: высота = [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:

Ввод: высота = [4,2,0,3,2,5]

выход: 9

намекать:

n == height.length

0 <= n <= 3 * 104

0 <= height[i] <= 105

Прочитав предыдущую статью, давайте сделаем четыре шага

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

1.1 Компонент динамического программирования 1: определение состояния

Проще говоря, при решении динамического программирования вам нужно открыть массив, что представляет собой каждый элемент массива f[i] или f[i][j] аналогично тому, что представляют x, y, z в математических задачах.

wc, вы говорите о том, как решить использовать динамическое программирование для этого?

  • Глядя на название, нужно постепенно проверять наибольшую длину
  • Ограничения по пространственной сложности нет, вы можете выбрать >=Вкл.
  • Как и в предыдущем вопросе, необходимо учитывать наибольшую высоту каждой ступени, чтобы принять низкую высоту, потому что могут образовываться низкие
  • Попробуйте написать уравнение перехода в виде шагов

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

Решение динамического программирования требует двух знаний:

  • последний шаг
  • подзадача

последний шаг

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

Сначала посмотрите слева направо, найдите максимальную высоту (глубину) каждой позиции

image.png

Глядя справа налево, найдите максимальную высоту каждой позиции.

423.jpg

Посмотрим на эффект после их наложения

424.jpg

чтобы каждое местомин - высотаЭто значение запасов воды в каждом месте.

подзадача

Сохраняем максимальное значение для каждой позиции слева направо и справа налево

Из наложения видно, что последняя позиция имеет минимальное значение 2 минус высота, а значение хранения равно 0.

1.2 Компонент динамического программирования 2:передаточное уравнение

ans += Math.min(left_max[i], right_max[i]) - height[i];

1.3 Компонент динамического программирования 3:Начальные условия и граничные случаи

1.4 Компонент динамического программирования 4:Порядок расчета

Слева направо + справа налево

Его временная сложность включена, и его пространственная сложность также включена.

Конечно, есть и другие решения, такие как стек

Код ссылки

public int trap(int[] height) {
    if (height == null || height.length == 0)
        return 0;
    int ans = 0;
    int size = height.length;
    int[] left_max = new int[size];
    int[] right_max = new int[size];
    left_max[0] = height[0];
    for (int i = 1; i < size; i++) {
        left_max[i] = Math.max(height[i], left_max[i - 1]);
    }
    right_max[size - 1] = height[size - 1];
    for (int i = size - 2; i >= 0; i--) {
        right_max[i] = Math.max(height[i], right_max[i + 1]);
    }
    for (int i = 1; i < size - 1; i++) {
        ans += Math.min(left_max[i], right_max[i]) - height[i];
    }
    return ans;
}

@Test
public void istrap() {
    int[] candidates = {2, 0, 6, 1};
    int i = trap(candidates);
    Assert.assertNotNull(i);
}

Популярная рекомендация:

В конце статьи мы недавно составили материал для интервью «Руководство по прохождению интервью по Java», в котором рассматриваются основные технологии Java, JVM, параллелизм Java, SSM, микросервисы, базы данных, структуры данных и многое другое. способ получения:GitHub GitHub.com/ting с -note…, и еще больше контента впереди.

Категории