«Сяо Ван, Сяо Чжан и Сяо Чжао — хорошие друзья. Один из них ушел в море, чтобы заняться бизнесом, один поступил в ключевой университет, а другой пошел в армию. Кроме того, они также знают следующие условия: Сяо Чжао старше солдат. Большой; возраст студента колледжа моложе, чем возраст Сяо Чжана; возраст Сяо Вана не совпадает с возрастом студента колледжа. Пожалуйста, узнайте, кто из этих трех бизнесменов люди?Кто студент колледжа?Кто солдат?
Цель этой статьи — записать некоторые обучающие вопросы о dp. Если вы не знакомы с динамическим программированием, перейдите к этой статье.
----
Как я объяснил динамическое программирование своей 5-летней племяннице?
----
Путь к чистке вопросов — долгий путь.
Какие вопросы вы можете решить с помощью динамического программирования?
1. Считать
- Сколько способов попасть в правый нижний угол
- Сколькими способами можно выбрать k чисел да и сложить
2. Найдите максимальное и минимальное значения
- Максимальная сумма чисел пути из левого верхнего угла в правый нижний угол
- самая длинная восходящая длина подпоследовательности
3. Ищите существования
- В игре со сбором камней обязательно ли выиграет тот, кто сделает первый ход?
- Можно ли выбрать k чисел так, чтобы сумма была суммой
Тема 1
63. Разные пути 2
Робот расположен в верхнем левом углу сетки m x n (начальная точка отмечена как «Старт» на изображении ниже).
Робот может двигаться вниз или вправо только на один шаг за раз. Робот пытается достичь правого нижнего угла сетки (помеченного «Готово» на изображении ниже).
Теперь учтите, что в сетке есть препятствия. Итак, сколько различных путей будет из верхнего левого угла в нижний правый угол?
Препятствия и пустые позиции в сетке представлены 1 и 0 соответственно.
Пример 1:
Вход: Сетка препятствий = [[0,0,0],[0,1,0],[0,0,0]]
выход: 2
объяснять:
В середине сетки 3x3 есть препятствие.
Есть 2 разных пути из левого верхнего угла в правый нижний угол:
\1. Вправо -> Вправо -> Вниз -> Вниз
\2. Вниз -> Вниз -> Вправо -> Вправо
Пример 2:
Вход: препятствияGrid = [[0,1],[0,0]]
выход: 1
намекать:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
препятствияGrid[i][j] равно 0 или 1
Эта тема и
---
Как я объяснил динамическое программирование своей 5-летней племяннице?
---
Различные пути 1 в приведенном выше примере примерно такие же, за исключением того, что добавлены препятствия.Мы можем судить, что препятствий нет.
2.1 Компонент динамического программирования 1: определение состояния
последний шаг
Неважно, как робот доберется до правого нижнего угла, всегда остается последний ход: - вправо или вниз
Если показано, мы устанавливаем координаты нижнего правого угла как (m-1,n-1)
Тогда позиция робота на предыдущем шаге последнего шага будет (m-2, n-1) или (m-1, n-2)
подзадача
Тогда, если у робота есть x способов пройти из левого верхнего угла в (m-2,n-1) и Y способов пройти из левого верхнего угла в (m-1,n-2), то робот имеет X+Y путей к (m-1,n-1)
Вопрос превращается в то, сколько способов робот может пройти из верхнего левого угла в (m-2,n-1) или (m-1,m-2)
Если вы перейдете к (m-2,n-1), как показано на рисунке:
Мы можем просто убить последнюю колонку
Точно так же, если вы переходите на строку (m-1, n-2), уменьшите одну строку.
государство:
Пусть f[i][j] будет количеством способов, которыми робот может пройти из левого верхнего угла в (i,j)
2.2 Компонент динамического программирования 2: уравнения перехода
Для любой сетки:
f[i][j] = f[i-1][j] + f[i][j-1]
1 2 3
1 показывает, сколько путей робот может пройти до [i][j]
2 показывает, сколько способов робот может пройти до f[i-1][j]
3 показывает, сколько способов робот может пройти до f[i][j-1]
2.3 Компонент динамического программирования 3: начальные условия и граничные случаи
Начальное условие: f[0][0]=1, так как у робота есть только один путь в левый верхний угол
Граничная ситуация: i=0 или j=0, тогда предыдущий шаг может идти только в одном направлении, то есть в 0-й строке или 0-м столбце, для каждого шага есть только один случай, тогда f[i][ j] = 1, все остальные области удовлетворяют уравнению перехода.
Если встречается препятствие, f[i][j] = 0.
3.4 Компонент динамического программирования 4: Порядок вычислений
Считать по ряду, зачем считать по ряду?
Для этого вопроса, когда f[1][1] вычисляется по строке, были вычислены как f[0][1], так и f[1][0], а две координаты также вычисляются по столбцу. надо заново считать.
- f[0][0] = 1, если первое препятствие f[0][0]=0
- Вычислить строку 0: f[0][0],f[0][1],...,f[0][n-1]
- Вычислить строку 1: f[1][0],f[1][1],...,f[1][n-1]
- ...
- Вычислить строку m-1: f[m-1][0],f[m-1][1],...,f[m-1][n-1]
Временная сложность: O(mn)
Код ссылки
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0) {
return 0;
}
// 定义 dp 数组并初始化第 1 行和第 1 列。
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 1;
}
// 根据状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 进行递推。
for (int i = 1; i < m; i++) {
for (int 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];
}
Коротко о версии скользящего массива. Когда мы знаем максимальное количество путей в текущей позиции, мы идем, чтобы найти количество путей в следующей позиции. Нам нужно знать только левый и верхний. Пространственная сложность о (м)
Код ссылки
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length, m = obstacleGrid[0].length;
int[] f = new int[m];
f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (obstacleGrid[i][j] == 1) {
f[j] = 0;
} else
if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
f[j] += f[j - 1];
}
}
}
return f[m - 1];
}
Популярная рекомендация:
-
Как я объяснил динамическое программирование своей 5-летней племяннице?
-
[День динамического программирования первый — самая длинная подстрока палиндрома]
-
[Второй день динамического программирования — сопоставление регулярных выражений]
-
[Динамическое программирование, день четвертый — поймать дождь]
-
[Пятый день динамического программирования — сопоставление подстановочных знаков]
В конце статьи мы недавно составили материал для интервью «Руководство по прохождению интервью по Java», в котором рассматриваются основные технологии Java, JVM, параллелизм Java, SSM, микросервисы, базы данных, структуры данных и многое другое. способ получения:GitHub GitHub.com/ting с -note…, и еще больше контента впереди.