Статья впервые опубликована на:GitHub.com/US TB-Вуд, умри, о ты…
написать впереди
Теперь, когда конкуренция становится все более жесткой, дни, когда на собеседованиях по передовым алгоритмам спрашивали только о сортировке, прошли. Теперь крупные компании любят задавать сложные вопросы по алгоритмам, такие как «динамическое программирование» — идея алгоритма, которая сегодня часто появляется на собеседованиях, но ее трудно понять.
Вот некоторые распространенные вопросы на собеседовании:
- Если на лестнице n ступенек, то за один раз можно пройти 1 или 2 ступени.Сколько существует способов пройти эти n ступенек (реализация динамического программирования)❓
- Как показано ниже: робот расположен в m x n верхнем левом углу сетки (начальная точка под фигурой с надписью «Старт»). Робот может двигаться только на один шаг вправо или вниз. Робот пытается достичь нижнего правого угла сетки (на следующем рисунке обозначено «Готово»). Теперь рассмотрим препятствия сетки. Что ж, из верхнего левого угла в нижний правый угол будет несколько разных путей ❓
- Выньте несколько предметов из M элементов и поместите их в рюкзак размера W. Объем каждого элемента W1, W2, W3 ... WN, а значения, соответствующие этим пунктам, являются P1, P2, P3 .. , ... PN, как найти максимальное значение, которое может держать этот рюкзак
Приведенные выше вопросы — очень распространенные вопросы по динамическому программированию.Вы можете сначала подумать, как ответить на приведенные выше вопросы🤔, а затем прочитать следующий контент с ответами.
Что такое динамическое программирование❓
Динамическое программирование, на английском языке это динамическое программирование, именуемое DP, хорошо решает «многоэтапные проблемы принятия решений», используя рекурсивную связь каждого этапа для определения оптимального решения каждого этапа один за другим и, наконец, получить оптимальное решение исходной проблемы.
Динамическое программирование и рекурсия
- Динамическое программирование не является рекурсивным по своей природе и может даже рассматриваться как идея разработки алгоритма, противоположная рекурсии.
- Рекурсия идет сверху вниз, начиная сверху, чтобы разложить проблему, а затем решить всю проблему, решая небольшие проблемы, которые разлагаются.
- Динамическое программирование осуществляется снизу вверх, начиная снизу для решения проблемы и постепенно расширяя масштаб проблемы для решения всей проблемы.
Давайте сначала рассмотрим вопрос интервью: Если на лестнице n ступенек, вы можете пройти 1 или 2 ступени за раз. Сколько способов вы можете пройти после n ступеней? Как анализировать этот вопрос, вы можете прочитать у автора предыдущий абзац Статьи, написанные по времени:Поговорим о фронтенд-алгоритме интервью — рекурсия
Первый метод: рекурсия грубой силы
function climbStairs(n) {
if (n == 1) return 1
if (n == 2) return 2
return climbStairs(n-1) + climbStairs(n-2)
}
Метод перебора рекурсии прост для понимания, но очень неэффективен, мы можем посмотреть на его дерево рекурсии:
Как понять это дерево рекурсии? Это нисходящий метод.Если мы хотим найти f (10), мы должны сначала найти подзадачи f (9) и f (8) и удовлетворить f (10) = f (9) + f ( 8), таким же образом f(9)=f(8)+f(7), f(8)=f(7)+f(6), f(3)=f( 2)+f( 1). Наконец, когда встречается f(2) или f(1), получается полное рекурсивное дерево, которое на самом деле является бинарным деревом.
Какова временная сложность рекурсивного алгоритма? Умножьте количество подзадач на время, необходимое для решения подзадачи.
Как видно из рисунка выше, по мере роста размера задачи это экспоненциальный алгоритм с временной сложностью O(2^n). Взяв f(10) выше в качестве примера, рекурсия грубой силы имеет большое количество подзадач, которые многократно вычисляются. f(7) вычисляется 2 раза, f(6) вычисляется 4 раза, и при каждом вычислении верхнего слоя вычисляются как f(1), так и f(2) нижнего слоя, видно, что это крайне неэффективная практика. Есть ли способ улучшить его?
Второй способ: плюс операция запоминания, то есть рекурсия заметки
Поскольку фундаментальная причина неэффективности рекурсии грубой силы заключается в том, что существует большое количество подзадач, которые многократно вычисляются, можно ли кэшировать эти подзадачи? Поместите эти подзадачи в определенную структуру данных.При вычислении подзадачи сначала проверьте структуру данных.Если есть кеш, верните его напрямую. Если кеша нет, закэшируйте этот подвопрос для удобства следующего использования. Это оптимизирует, почему рекурсия грубой силы неэффективна.
var calculated = []
function climbStairs(n) {
if(n == 1) {
return 1
}else if (n == 2) {
return 2
}else {
if(!calculated[n-1]){
calculated[n-1] = climbStairs(n-1)
}
if(!calculated[n-2]){
calculated[n-2] = climbStairs(n-2)
}
return calculated[n-1] + calculated[n-2]
}
}
Давайте посмотрим, какова временная сложность? Благодаря операции запоминания огромное рекурсивное дерево «обрезается», а подзадачи, которые необходимо повторно вычислять, кэшируются.Нет избыточных вычислений.Временная сложность пропорциональна размеру задачи, которая составляет O( н).
Третий способ: динамическое программирование
Динамическое программирование должно соответствовать трем условиям:оптимальная подзадача,Граничные условияа такжеуравнение перехода состояния
1. Оптимальная подзадача
f(10)=f(9)+f(8), что является оптимальной подзадачей задачи f(10), если найдена оптимальная подзадача f(9) и f(8), то есть f(10) ) — оптимальная подзадача
2. граничные условия
Динамическое программирование — это нисходящая идея проектирования.В качестве примера возьмем подъем по лестнице, граничные условия, разложенные на нижний слой, будут f(1)=1, f(2)=2.
3. Уравнение перехода состояния
На самом деле самый сложный шаг в динамическом программировании — написать уравнение перехода состояния, так как же написать уравнение перехода состояния? Уравнение перехода состояния можно понимать как математическое уравнение, описывающее математическую задачу.Для задачи подъема по лестнице можно найти уравнение перехода состояния f[i]=f[i-1]+f[i-2 ], начиная с самого начала Начать с двух состояний, 1 и 2 шагов, и решить снизу вверх:
function climbStairs(n) {
var val = [];
for ( var i = 0; i <= n ; ++i) {
val[i] = 0
}
if (n <= 2) {
return n
} else {
val[1] = 1
val[2] = 2
for (var i = 3; i <= n; ++i) {
val[i] = val[i-1] + val[i-2]
}
return val[n]
}
}
console.log(climbStairs(10)) // 55
Вопрос интервью 2: вопросы о разных путях
Как показано на рисунке ниже: Робот расположен в верхнем левом углу сетки m x n (начальная точка отмечена как «Старт» на рисунке ниже). Робот может двигаться вниз или вправо только на один шаг за раз. Робот пытается достичь нижнего правого угла сетки (помеченного «Готово» на изображении ниже). Теперь учтите, что в сетке есть препятствия. Итак, сколько разных путей будет из верхнего левого угла в нижний правый угол❓
этоleetcodeЕсли вы столкнетесь с этим вопросом в интервью, как вы должны ответить на него? Помните о трех элементах динамического программирования, упомянутых выше❓
1. Оптимальная подзадача
Динамическое программирование — это мышление снизу вверх, что может противоречить тому, что думает большинство людей. Как показано на рисунке выше, если мы хотим достичь конечной точки F(7*3), есть только два случая: один для F(7*2) делает один шаг вниз, а другой для F( 6*3), чтобы сделать один шаг вправо. Таким образом, мы можем сделать вывод, что оптимальными подзадачами для достижения конца являются F (7 * 2) и F (6 * 3).
2. Уравнение перехода состояния
Согласно анализу оптимальной подзадачи, легко составить уравнение перехода состояния в виде F(m*n) = F((m-1)*n) + F(m*(n-1) ).
3. Граничные условия
- Если есть только 1 строка, пройти первую строку.Если есть точка сетки с начальным значением 1, это означает, что в текущем узле есть препятствие, и путь не может пройти через него.Установите значение на 0;
- Если есть только 1 столбец, пройти по первому столбцу.Если есть точка сетки с начальным значением 1, это означает, что текущий узел имеет препятствие и через него нельзя пройти.Установите значение на 0;
var uniquePathsWithObstacles = function(arr) {
// arr为二维数组，m为行，n为列
let n = arr.length, m = arr[0].length;
let temp = [];
// 初始化将格子填充为0
for (let i = 0; i < n; i++) {
temp[i] = Array(m).fill(0)
}
// 如果起始或终止目标有障碍物，则直接返回0
if (arr[0][0] == 1 || arr[n - 1][m - 1] == 1) {
return 0
}
// 遍历二维数组的列数
for (i = 0; i < n; i++) {
// 遍历二维数组的行数
for (let j = 0; j < m; j++) {
if (i == 0 && j == 0) {
temp[i][j] = 1;
// 第一种边界情况：1行n列
} else if (i == 0) {
if (arr[i][j] != 1 && temp[i][j - 1] != 0) {
temp[i][j] = 1;
} else {
temp[i][j] = 0;
}
// 第二种边界情况： m行1列
} else if (j == 0) {
if (arr[i][j] != 1 && temp[i - 1][j] != 0) {
temp[i][j] = 1;
} else {
temp[i][j] = 0;
}
} else if (arr[i][j] != 1) {
// 如果不是上述的两种边界情况，终止条件的到达方式是i-1,j和i,j-1的和
temp[i][j] = temp[i - 1][j] + temp[i][j - 1]
}
}
}
return temp[n - 1][m - 1]
};
console.log(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])) // 2
Интервью 3: Вопрос о рюкзаке
Выньте несколько предметов из M предметов и положите их в рюкзак размера W. Объем каждого предмета равен W1, W2, W3... Wn, а значения, соответствующие этим предметам, равны P1, P2, P3.. ...Пн, как найти максимальное значение, которое может вместить этот рюкзак❓
function beibao(M, W, arrP, arrW) {
var result = []
for (var i = 0; i <= M; i++) {
result[i] = []
for (var j = 0; j <= W; j++) {
if ( i == 0) {
result[i][j] = 0
} else if ( arrW[i-1] > j) {
result[i][j] = result[i-1][j]
} else {
result[i][j] = Math.max(arrP[i-1] + result[i-1][j - arrW[i-1]], result[i-1][j])
}
}
}
return result[i-1][j-1]
}
var M = 5; // 物体个数
var W = 16; // 背包总容量
var arrP = [4,5,10,11,13]; // 物体价值
var arrW = [3,4,7,8,9]; // 物体个数
console.log(beibao(M, W, arrP, arrW)); // 23
Суммировать
Динамическое программирование подходит для решения перекрывающихся подзадач и оптимальных свойств подструктуры. Три элемента: «оптимальные подзадачи», «граничные условия» и «уравнения перехода состояний». Ключом к решению таких проблем, как динамическое программирование, является запись «уравнения перехода состояний». , а идея написания метода уравнения перехода состояний такова:
- найти оптимальную подзадачу
- Напишите уравнение перехода состояния
- Преобразуйте уравнения перехода состояния в код
Можете обратить внимание на мой паблик-аккаунт «Muchen Classmate», фермера на гусиной фабрике, который обычно записывает какие-то банальные мелочи, технологии, жизнь, инсайты и срастается.