Динамическое программирование примеры

В информатике есть несколько способов описания подхода к решению алгоритма. Жадный, наивный, разделяй и властвуй — всё это способы решения алгоритмов. Один из таких способов называется динамическим программированием (DP). В этой статье мы рассмотрим, что такое динамическое программирование, его характеристики и два основных подхода к решению алгоритмов с помощью DP.

Что такое динамическое программирование?

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

Скажем, например, у нас есть рюкзак, в который может поместиться только определённое количество предметов. Какая комбинация предметов даст нам максимальную ценность? Или предположим, что у нас есть рюкзак определённой грузоподъёмности. Какая комбинация предметов с заданным весом даст нам максимальную ценность?

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

Наивные решения

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

Нисходящие решения

Это первый способ использования динамического программирования в вашем решении. Нисходящее решение возьмёт наивное решение, использующее рекурсию, а затем добавит метод, называемый мемоизацией, для его оптимизации. Мемоизация действует как своего рода кеш для хранения наших подзадач по мере продвижения, чтобы алгоритм работал быстрее. Обычно это происходит в форме объекта или словаря.

Решения снизу-вверх

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

Давайте посмотрим на две общие проблемы в каждом из подходов: Фибоначчи и самая длинная общая подстрока .

Фибоначчи

Последовательность Фибоначчи — это последовательность чисел, каждое из которых представляет собой сумму двух предыдущих чисел, начиная с 0 и 1:

Fn = 0, 1, 1, 2, 3, 5, 8, 13, 21…и т.д.
0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21
13 + 21 = 34…и т.д.

Подсказка

По заданному числу n найдите n- е число в последовательности Фибоначчи.

Решение 1. Наивно

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

Пример наивного решения для Фибоначчи выглядит так:

const fibNaive = (num) => {
if(num < 2) {
return num;
}

return fibNaive(num — 1) + fibNaive(num — 2);
};

Вначале это выглядит довольно просто и понятно. Мы используем рекурсию для решения этой проблемы. Наш базовый случай возвращает число, если оно меньше двух. В противном случае он использует рекурсию для получения числа, добавляя каждый вызов в стек, пока мы не достигнем базового случая. Затем он складывает все вызовы вместе, чтобы получить наш результат. Поскольку у нас есть время выполнения двух операций, это то, что мы называем временем выполнения O (2 n). Мы измеряем качество решения по нотации Big O Notation . Это неэффективное решение из-за времени выполнения, и его следует избегать любой ценой nthn.

Решение 2. Подход к динамическому программированию № 1 — сверху вниз с мемоизацией

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

const fibMemo = (num, memo = { 0: 0, 1: 1 }) => {
if(num < 2) {
return memo[num];
}

let result = fibMemo(num — 1, memo) + fibMemo(num — 2, memo);
if(!memo[num]) {
memo[num] = result;
}

return result;

}

Основное решение здесь то же самое. Но мы изменили его, добавив словарь, который будет содержать наши значения Фибоначчи, когда мы проходим рекурсию. Каждый раз n, когда изменяется, мы добавляем значение к memo объекту, переданному в fibMemo функцию.

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

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

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

Это решение изменяет временную сложность с O (2 n) на O (n).

Решение 3. Подход к динамическому программированию № 2 — снизу-вверх с табуляцией

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

const fibTab = (num) => {
let fibDict = { 1:0, 2:1 };

for(let i = 3; i <= num; i++) {
if(!fibDict[i]){
fibDict[i] = fibDict[i — 1] + fibDict[i — 2];
}
}
return fibDict[num];
}

Как и мемоизированная версия, эта версия — время выполнения O (n), потому что в этом сценарии мы перебираем каждое число между 1…n

Затем давайте взглянем на другую распространённую проблему, называемую самой длинной общей подстрокой.

ЧИТАЙТЕ ТАКЖЕ: Языки объектно-ориентированного программирования.

Самая длинная общая подстрока

Если даны две строки, найдите длину самой длинной общей подстроки.

Самая длинная общая подстрока в «ABABC» и «CABAB» будет иметь «ABAB» длину 4, потому что мы видим «ABAB» в обеих строках.

Решение 1. Наивное решение

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

const naiveSub = (str1, str2) => {
//find all the substrings.
substrs = [];
maxString = «»;
otherString = «»;
if(str1.length > str2.length) {
maxString = str1;
otherString = str2;
} else {
maxString = str2;
otherString = str1;
}

for(let i = 0; i < maxString.length — 1; i++) {
let str = «»;
str += maxString[i];
for(let j = i + 1; j < maxString.length; j++) {
str += maxString[j];
substrs.push(str);
}
} // O(n) * O(n) === O(n^2)
//have all substrings
//see if other string has any of values from array in it.

let maxLength = 0;
let maxSubStr = «»;

substrs.forEach(string => { // O(m)
if(new RegExp(string).test(otherString)) {
if(maxLength < string.length) {
maxLength = string.length;
maxSubStr = string;
}
}
});
return [ maxLength, maxSubStr ];
} // O(n^2 + m) <== Big O Notation for Naive Solution

console.log(naiveSub(«ABABC», «CABAB»));

Временная сложность наивного решения учитывает размер как массива подстрок, так и строк. Вложенный цикл for равен O (n 2) , а цикл forEach — O (m) . Это связано с тем, что длина массива может отличаться от длины строк. Поскольку два основных блока кода сложены, мы складываем временные сложности вместе. Последний Big O равен O (n 2 + m). Хотя наивное решение может быть не лучшим решением, оно работает и поможет вам найти более эффективные решения.

Решение 2. Нисходящее решение с рекурсией

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

const topDown = (str1, str2, count = 0) => {

let i = str1.length;
let j = str2.length;
//if the strings don’t exist, return 0
if(i === 0 || j === 0) {
return count;
}

if(str1[i — 1] === str2[j — 1]) { // if the chars are the same, up the count and shorten string by 1
count = topDown(str1.slice(0, i — 1), str2.slice(0, j — 1), count + 1);
}
count = Math.max(count, //max between count and the other function
Math.max( // max between looking at shortening one word vs shortening the other word.
topDown(str1.slice(0, i), str2.slice(0, j — 1), 0),
topDown(str1.slice(0, i — 1), str2.slice(0, j), 0)));

return count;
}

console.log(topDown(‘alphabetical’, ‘abcada’));

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

Решение 3. Восходящее решение с табуляцией

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

const create2DArray = (A, B) => {
const table = [];

for (let i = 0; i <= A.length; i += 1) {
table.push([]);
for (let j = 0; j <= B.length; j += 1) {
table[i].push(0);
}
}
return table;
};

Если наши строки «techcareer»и «tech career»наша пустая таблица будет выглядеть так:

[
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
]

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

const bottomUp = (A, B) => {
let table = create2DArray(A, B); // create the table
let max = 0; // initialize and declare max substring length to be 0
//start i and j at 1 so we can compare characters to previous row and column
for (let i = 1; i < A.length + 1; i += 1) {
for (let j = 1; j < B.length + 1; j += 1) {
//our initial row and column is set to 0
if (i === 0 || j === 0) {
table[i][j] = 0;
}
//if our strings chars are the same in the prev place
else if (A[i — 1] === B[j — 1]) {
//assign this spot in table to the table[i — 1][j — 1]’s value + 1
table[i][j] = table[i — 1][j — 1] + 1;
max = Math.max(max, table[i][j]); //compare the max to the new value at table[i][j] and reassign to max
} else {
table[i][j] = 0; //if the chars are not the same, it will reset count to 0. We still keep track of the max seen so far.
}
}
}
return max;
};
let str1 = ‘techcareer’;
let str2 = ‘tech career’;
console.log(bottomUp(str1, str2));

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

Заключение

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

ЧИТАЙТЕ ТАКЖЕ: 

• Основы программирования для начинающих.
• Лучший язык программирования для создания игр.