Эта ссылка на блогРад двигаться, учительская «js-версия структуры данных и алгоритма»Часть 1 адаптирована из «Комического алгоритма». Автор оригинала: программист Сяо Хуэй.
предисловие
За последние два года, с усилением конкуренции в интернет-индустрии, требования к алгоритмам для клиентских позиций на рынке также в определенной степени возросли.
Я помню, что, когда я участвовал в собеседовании при приеме на работу в кампусе Tencent на первом курсе, я подготовил только несколько общих алгоритмов сортировки, чтобы справиться с этим, однако в этом году многие крупные компании, включая Toutiao, появились в письменных тестовых вопросах переднего плана. "как дела""динамическое программирование""Алгоритм разделяй и властвуй«И другие сложные алгоритмические задачи. Не так-то просто разобраться с такими сложными алгоритмическими проблемами на месте без предварительной подготовки.
Этот блог будет разделен на две части
- Часть 1: Рассказываем через комиксыдинамическое программированиеподумал о
- Часть 2. Сотрудничество с соответствующим динамическим программированиемLeetCode ЖентиПроводить практические занятия
Я верю, что после прочтения вы досконально усвоите метод динамического программирования и научитесь гибко его использовать.
Часть 1: Комическое понимание
11111111111111111111111
тема:
Например, ставить по 1 книге и ставить всего 10 раз, это один из способов. Мы можем сократить его как 1,1,1,1,1,1,1,1,1,1.
Для другого примера кладите по 2 книги за раз, всего 5 раз, это еще один метод. Мы можем сократить его как 2,2,2,2,2.
Конечно, есть много, много других способов.
11111111111111111111111
Первый:
Второй:
Для вашего удобства вот еще один пример:
Как показано на рисунке, предполагается, что до конечной точки можно добраться только по двум путям: дорога1 или дорога2.
(Это эквивалентно разделению последнего шага размещения книги на две ситуации: размещение 2 книг и размещение 1 книги)
Есть x путей, чтобы добраться до дороги1 (эквивалентно количеству релизов F(8) от 0 до 8)
Есть y путей к дороге2 (эквивалентно количеству выпусков от 0 до 9 F(9))
Тогда вероятность достижения конечной точки равна x+y (то есть F(10) = F(9)+F(8), которую мы получили ранее)
F(1) = 1;
F(2) = 2;
F(n) = F(n-1)+F(n-2) (n>=3)
Я считаю, что после прочтения у вас должно быть предварительное представление о динамическом программировании.
Здесь вы можете сначала попробовать написать код для этой задачи.
Далее, давайте углубим наше понимание динамического программирования с помощью актуального вопроса LeetCode.
Часть 2: Практическое упражнение
Другой путь II
LeetCode Вопрос 63Оригинальный титульный адрес
Сложность вопросов средняя
Описание темы
Робот расположен в верхнем левом углу сетки m x n (начальная точка отмечена как «Старт» на изображении ниже).
Робот может двигаться вниз или вправо только на один шаг за раз. Робот пытается достичь правого нижнего угла сетки (помеченного «Готово» на изображении ниже).
Теперь учтите, что в сетке есть препятствия. Итак, сколько различных путей будет из верхнего левого угла в нижний правый угол?
Препятствия и пустые позиции в сетке соответственно1а также0Представлять.
проиллюстрировать:Значение m и n не превышает 100.
Пример 1
войти:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
выход: 2
объяснять: В середине сетки 3x3 есть препятствие.
Есть 2 разных пути из левого верхнего угла в правый нижний угол:
1. Вправо -> Вправо -> Вниз -> Вниз
2. Вниз -> Вниз -> Вправо -> Вправо
Тематический анализ
Я считаю, что все уже видели, и наши вопросы почти соответствуют темам, показанным в наших комиксах.
Но это немного усложняет задачу, и нам нужно учитывать препятствия.
Помните о трех элементах динамического программирования, о которых мы упоминали ранее.[Оптимальная подструктура] [граница] и [формула перехода состояния]?
В качестве примера возьмем приведенную в заголовке картинку:
Не учитывая препятствий, мы используем идею динамического программирования, чтобы достичь конечной точки в нескольких ситуациях?
Очевидно, что два вида: прибытие сверху конечной точки или слева от конечной точки
матрица 7*3
Тогда мы можем легко получить конечную точку F(7*3) этой матрицы 7*3.оптимальное основаниедля F(6*3) и F(7*2)
пока что этоФормула перехода состоянияЭто также ясно с первого взгляда: F(m*n) = F(m-1*n) + F(m*n-1)
Наконец, мы рассмотрим его крайние случаи:
Фактически, после исправления студентов в области комментариев рассмотренные нами ранее граничные условия F(2*2) также можно разделить на два случая: один столбец и одна строка, то есть F(1*2) + Ф(2*1).
Все матрицы F(m*n), наконец, могут быть разбиты на одну строку и один столбец, поэтому здесь у нас есть только два граничных случая.
- Первая граница F(1*n) состоит из 1 строки и n столбцов.
- Вторая граница F(n*1) — это n строк и 1 столбец.
Код
export default (arr) => {
let dp = (m, n) => {
// 检查起始或者目标元素是不是1(障碍物)，如果起始或者最后那个格就是1，说明怎么都怎么不到那，
// 直接返回0
if (arr[m - 1][n - 1] === 1 || arr[0][0] === 1) {
return 0
}
// 有边界
if (m < 2 || n < 2) {
// 第一种边界 1行n列
if (m < 2) {
return arr[m - 1].includes(1) ? 0 : 1
} else {
// 第二种边界 n行1列
for (let i = 0; i < m; i++) {
if (arr[i][0] === 1) {
return 0
}
}
return 1
}
} else {
// 递归
return dp(m - 1, n) + dp(m, n - 1)
}
}
return dp(arr.length, arr[0].length)
}Дополнение: анализ временной сложности
анализ проблемы
Спасибо за ваши вопросы в разделе комментариев
Во-первых, с нашим кодом выше нет проблем, но превышен лимит времени на 27-м тестовом примере на LeetCode.
Этот тестовый пример относительно сложен и представляет собой двумерную матрицу 33 * 22.
Когда матрица, почему наш подход к достижению определенного отрезка времени сложности слишком высок, не так ли?
Давайте сначала рассмотрим наше предыдущее мышление:
- F(10) = F(9) + F(8)
- F(9) = F(8) + F(7)
После разложения F(9) F(10) можно записать как
- F(8) + F(8) + F(7)
И F(8) = F(7) + F(6)
Затем продолжайте разлагать F (8), и F (10) можно записать как
- F(7) + F(7) +F(7) + F(6) + F(6)
Ты заметил?
Чем дальше вниз по делению, тем больше повторений, может быть, вы подумаете, что нужно просто добавить значение F(n) еще раз?
Но здесь я должен напомнить вам, что:
F(n) — это не просто ссылка на значение, это рекурсивная функция, и она будет повторно выполнять функцию F каждый раз, когда мы ее повторяем.
Мы не обсуждаем, как рассчитать временную сложность
Но здесь я могу вам сказать, что временная сложность нашего предыдущего метода составляет O (2 ^ n)
Итак, как его улучшить?
придумывать идеи
В двух идеях, представленных здесь, вы также можете попытаться написать о:
- Кэшировать каждое вычисляемое значение, то есть значение F(9), f(8), f(7)..., каждый раз вычисляет данные непосредственно до значения, не повторяя повторный вызов рекурсивной функции.
- Вычисление снизу вверх (от начальной точки до конечной точки), поскольку оно каждый раз зависит только от первых двух данных, достаточно сохранить только первые два данных через две переменные.Например, вычисление F(3) зависит только от F(1) и F(2), вычисление F(6) зависит только от F(5) и F(4).
Оптимизация кода
// 传入二维数组
arr => {
// 行数
let n = arr.length;
if(!n){
return 0;
}
// 列数
let m = arr[0].length;
// 起点或终点为障碍物
if(arr[0][0] === 1 || arr[n - 1][m - 1] === 1){
return 0;
}
// 记录到达每个位置的路径可能数
var rode= [];
// 遍历每一行
for(let i = 0; i < n; i++){
rode[i] = []; // 遍历每一行的每个元素
for(let j = 0; j < m; j++){
// 若某节点是障碍物，则通向该节点的路径数量为0
if(arr[i][j] === 1){
rode[i][j] = 0;
} else if(i === 0){
// 若是第一行 每个节点是否能通过都依赖它左方节点
rode[i][j] = rode[i][j - 1] === 0 ? 0 : 1;
} else if(j === 0){
// 若是第一列 每个节点是否能通过都依赖它上方节点
rode[i][j] = rode[i - 1][j] === 0 ? 0 : 1;
} else {
// 否则递归
rode[i][j] = rode[i - 1][j] + rode[i][j - 1];
}
}
}
return rode[n - 1][m - 1];
}Ссылаться на
- Программист Сяохуэй——Комикс: Что такое динамическое программирование?
- Сегодняшние заголовки рады двигаться, учитель - js версия структуры данных и алгоритма
- Вы также можете обратиться к дополнениям, сделанным FE_Yuan для этого блога:Алгоритм фронтенд-интервью — динамическое программирование
Суммировать
Все ли узнали, когда ты освоилдинамическое программированиетри элемента[Оптимальная подструктура] [граница] и [формула перехода состояния]
После этого несложно решить алгоритмическую задачу динамического программирования. Но идеи в нем должны быть переварены и усвоены нами.
Я верю, что вы сможете решить такие проблемы в будущем.