6 задач динамического программирования и решения для вашего следующего собеседования по кодированию
Эта статья основана на интерактивном курсе подготовки к собеседованию для разработчиков Grokking Dynamic Programming Patterns for Coding Interviews. Если вы получили пользу от этой статьи, ознакомьтесь с курсом, чтобы узнать о многих других проблемах и решениях, подобных этим.
— —
Многие программисты боятся вопросов динамического программирования (DP) в своих собеседованиях по программированию. Легко понять почему. Они тяжелые!
Во-первых, сложно понять алгоритмы динамического программирования. Любой опытный разработчик скажет вам, что для овладения DP требуется много практики. Это также требует способности разбить проблему на несколько компонентов и объединить их, чтобы получить решение.
Другая часть разочарования также связана с принятием решения, использовать ли DP для решения этих проблем. У большинства проблем есть несколько решений. Как найти правильный подход? Запоминать или повторять? Сверху вниз или снизу вверх?
Итак, мы раскроем некоторые из наиболее распространенных проблем DP, с которыми вы, вероятно, столкнетесь на собеседовании, представим базовое (или грубое) решение, а затем предложим одну технику DP (написанную на Java) для решения каждой проблемы. Вы сможете сравнивать и противопоставлять подходы, чтобы получить полное представление о проблеме и узнать оптимальные решения.
Звучит неплохо? Пойдем.
0–1 Задача о ранце
Учитывая вес и прибыль «N» предметов, положите их в рюкзак вместимостью «С». Ваша цель: получить максимальную прибыль от предметов в рюкзаке. Каждый элемент можно выбрать только один раз.
Типичный пример этой задачи оптимизации: какие плоды вы положите в рюкзак, чтобы получить максимальную прибыль. Вот вес и прибыль каждого фрукта:
Предметы: {яблоко, апельсин, банан, дыня}
Вес: {2, 3, 1, 4}
Прибыль: {4, 5, 3, 7}
Вместимость рюкзака: 5
Попробуем складывать в рюкзак разные комбинации фруктов, чтобы их общий вес был не более 5.
Яблоко + апельсин (общий вес 5) = ›9 прибыль
Apple + банан (общий вес 3) =› 7 прибыль
Апельсин + банан (общий вес 4) = ›8 прибыль
Банан + Дыня (общий вес 5) = ›10 прибыли
Это показывает, что банан + дыня - лучшая комбинация, так как она дает нам максимальную прибыль, а общий вес не превышает вместимости.
Эта проблема:
Имея два целочисленных массива для представления веса и прибыли «N» элементов, найдите подмножество этих элементов, которое принесет нам максимальную прибыль, так чтобы их совокупный вес не превышал заданное число «C». Каждый предмет можно выбрать только один раз, поэтому вы либо кладете предмет в рюкзак, либо нет.
Простое решение:
Базовое решение методом грубой силы может заключаться в том, чтобы попробовать все комбинации данных элементов (как мы делали выше), что позволит нам выбрать ту, которая дает максимальную прибыль и вес, не превышающий «C». Возьмем пример с четырьмя элементами (A, B, C и D). Чтобы попробовать все комбинации, алгоритм будет выглядеть так:
для каждого элемента "i"
создайте новый набор, включающий элемент «i», если общий вес не превышает допустимый, и
рекурсивно обработать оставшиеся элементы
создать новый набор без элемента «i» и рекурсивно обработать оставшиеся элементы
вернуть набор из двух вышеупомянутых наборов с более высокой прибылью
Вот код:
public class Knapsack {
public int solveKnapsack(int[] profits, int[] weights, int capacity) {
return this.knapsackRecursive(profits, weights, capacity, 0);
}
private int knapsackRecursive(int[] profits, int[] weights, int capacity, int currentIndex) {
// base checks
if (capacity <= 0 || currentIndex < 0 || currentIndex >= profits.length)
return 0;
// recursive call after choosing the element at the currentIndex
// if the weight of the element at currentIndex exceeds the capacity, we shouldn’t process this
int profit1 = 0;
if( weights[currentIndex] <= capacity )
profit1 = profits[currentIndex] + knapsackRecursive(profits, weights,
capacity — weights[currentIndex], currentIndex + 1);
// recursive call after excluding the element at the currentIndex
int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);
return Math.max(profit1, profit2);
}
public static void main(String[] args) {
Knapsack ks = new Knapsack();
int[] profits = {1, 6, 10, 16};
int[] weights = {1, 2, 3, 5};
int maxProfit = ks.solveKnapsack(profits, weights, 7);
System.out.println(maxProfit);
}
}
Временная сложность описанного выше алгоритма экспоненциальна O (2 ^ n), где «n» представляет собой общее количество элементов. Это также видно из приведенного выше дерева рекурсии. У нас есть в общей сложности «31» рекурсивный вызов - вычисленный через (2 ^ n) + (2 ^ n) -1, что асимптотически эквивалентно O (2 ^ n).
Сложность пространства - O (n). Это пространство используется для хранения стека рекурсии. Поскольку наш рекурсивный алгоритм работает по принципу «сначала глубина», в стеке вызовов может быть не более «n» рекурсивных вызовов в любой момент.
Один подход DP: сверху вниз с мемоизацией
Мы можем использовать подход, называемый мемоизацией, чтобы преодолеть перекрывающиеся подзадачи. Мемоизация - это когда мы сохраняем результаты всех ранее решенных подзадач и возвращаем результаты из памяти, если мы сталкиваемся с проблемой, которая уже решена.
Поскольку у нас есть два изменяющихся значения (capacity и currentIndex) в нашей рекурсивной функции knapsackRecursive (), мы можем использовать двумерный массив для хранения результатов всех решенных подзадач. Вам нужно будет хранить результаты для каждого подмассива (т.е. для каждого возможного индекса «i») и для каждой возможной емкости «c».
Вот код:
public class Knapsack {
public int solveKnapsack(int[] profits, int[] weights, int capacity) {
Integer[][] dp = new Integer[profits.length][capacity + 1];
return this.knapsackRecursive(dp, profits, weights, capacity, 0);
}
private int knapsackRecursive(Integer[][] dp, int[] profits, int[] weights, int capacity,
int currentIndex) {
// base checks
if (capacity <= 0 || currentIndex < 0 || currentIndex >= profits.length)
return 0;
// if we have already processed similar problem, return the result from memory
if(dp[currentIndex][capacity] != null)
return dp[currentIndex][capacity];
// recursive call after choosing the element at the currentIndex
// if the weight of the element at currentIndex exceeds the capacity, we shouldn’t process this
int profit1 = 0;
if( weights[currentIndex] <= capacity )
profit1 = profits[currentIndex] + knapsackRecursive(dp, profits, weights,
capacity — weights[currentIndex], currentIndex + 1);
// recursive call after excluding the element at the currentIndex
int profit2 = knapsackRecursive(dp, profits, weights, capacity, currentIndex + 1);
dp[currentIndex][capacity] = Math.max(profit1, profit2);
return dp[currentIndex][capacity];
}
public static void main(String[] args) {
Knapsack ks = new Knapsack();
int[] profits = {1, 6, 10, 16};
int[] weights = {1, 2, 3, 5};
int maxProfit = ks.solveKnapsack(profits, weights, 7);
System.out.println(maxProfit);
}
}
Какова временная и пространственная сложность вышеуказанного решения? Поскольку наш массив мемоизации dp [profits.length] [capacity + 1] хранит Результаты для всех подзадач, мы можем сделать вывод, что у нас не будет больше чем N * C подзадач (где «N» - количество элементов, а «C» - вместимость рюкзака). Это означает, что наша временная сложность будет O (N * C).
Вышеупомянутый алгоритм будет использовать пространство O (N * C) для массива мемоизации. В остальном мы будем использовать пространство O (N) для стека вызовов рекурсии. Таким образом, общая сложность пространства будет O (N * C + N), что асимптотически эквивалентно O (N * C).
Неограниченная задача о ранце
Учитывая вес и прибыль «N» предметов, положите их в рюкзак вместимостью «C». Ваша цель: получить максимальную прибыль от предметов в рюкзаке. Единственная разница между задачей о рюкзаке 0/1 и этой проблемой заключается в том, что нам разрешено использовать неограниченное количество предметов.
Используя пример из последней задачи, вот вес и прибыль от плодов:
Предметы: {яблоко, апельсин, дыня}
Вес: {1, 2, 3}
Прибыль: { 15, 20, 50}
Вместимость ранца: 5
Попробуйте разные комбинации фруктов в рюкзаке, чтобы их общий вес был не более 5.
5 яблок (общий вес 5) = ›75 прибыли
1 яблоко + 2 апельсина (общий вес 5) =› 55 прибыли
2 яблока + 1 дыня (общий вес 5) = ›80 прибыли
1 апельсин + 1 дыня (общий вес 5) = ›70 прибыли
2 яблока + 1 дыня - лучшая комбинация, так как она дает максимальную прибыль, а общий вес не превышает вместимости.
Эта проблема:
Имея два целочисленных массива, представляющих веса и прибыль «N» предметов, найдите подмножество этих предметов, которое принесет нам максимальную прибыль, так чтобы их совокупный вес не превышал заданное число «C». Вы можете предположить бесконечное количество товаров, поэтому каждый товар можно выбрать несколько раз.
Решение грубой силы:
Основное решение методом грубой силы может заключаться в том, чтобы попробовать все комбинации данных элементов, чтобы выбрать тот, который дает максимальную прибыль и вес, не превышающий «C». Вот как будет выглядеть наш алгоритм:
для каждого элемента "i"
создать новый набор, включающий одно количество элемента «i», если оно не превышает вместимость, и
рекурсивно вызывать для обработки всех элементов
создать новый набор без элемента «i» и рекурсивно обработать оставшиеся элементы
вернуть набор из двух вышеупомянутых наборов с более высокой прибылью
Единственная разница между задачей оптимизации рюкзака 0/1 и этой состоит в том, что после включения элемента мы рекурсивно вызываем для обработки все элементы (включая текущий элемент). В рюкзаке 0/1 мы рекурсивно вызываем для обработки оставшиеся элементы.
Вот код:
public class Knapsack {
public int solveKnapsack(int[] profits, int[] weights, int capacity) {
return this.knapsackRecursive(profits, weights, capacity, 0);
}
private int knapsackRecursive(int[] profits, int[] weights, int capacity, int currentIndex) {
// base checks
if (capacity <= 0 || profits.length == 0 || weights.length != profits.length ||
currentIndex < 0 || currentIndex >= profits.length)
return 0;
// recursive call after choosing the items at the currentIndex, note that we recursive call on all
// items as we did not increment currentIndex
int profit1 = 0;
if( weights[currentIndex] <= capacity )
profit1 = profits[currentIndex] + knapsackRecursive(profits, weights,
capacity — weights[currentIndex], currentIndex);
// recursive call after excluding the element at the currentIndex
int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);
return Math.max(profit1, profit2);
}
public static void main(String[] args) {
Knapsack ks = new Knapsack();
int[] profits = {15, 50, 60, 90};
int[] weights = {1, 3, 4, 5};
int maxProfit = ks.solveKnapsack(profits, weights, 8);
System.out.println(maxProfit);
}
}
Сложность описанного выше алгоритма во времени и пространстве экспоненциальна O (2 ^ n), где «n» представляет собой общее количество элементов.
Есть лучшее решение!
Одно решение DP: программирование снизу вверх
Давайте заполним наш массив «dp [] []» из приведенного выше решения, работая по восходящей схеме. Мы хотим «найти максимальную прибыль для каждого подмассива и для каждой возможной мощности».
Для каждой возможной емкости «c» (т. Е. 0 ‹= c‹ = емкость) есть два варианта:
- Исключить товар. Мы возьмем любую прибыль, которую получим от подмассива, за исключением этого элемента: dp [index-1] [c]
- Включите товар, если его вес не превышает "c". Мы включим его прибыль плюс любую прибыль, которую мы получим от оставшейся мощности: profit [index] + dp [index] [c-weight [index]]
Возьмите максимум из двух вышеупомянутых значений:
dp [index] [c] = max (dp [index-1] [c], profit [index] + dp [index] [c-weight [index]])
Вот код:
public class Knapsack {
public int solveKnapsack(int[] profits, int[] weights, int capacity) {
// base checks
if (capacity <= 0 || profits.length == 0 || weights.length != profits.length)
return 0;
int n = profits.length;
int[][] dp = new int[n][capacity + 1];
// populate the capacity=0 columns
for(int i=0; i < n; i++)
dp[i][0] = 0;
// process all sub-arrays for all capacities
for(int i=0; i < n; i++) {
for(int c=1; c <= capacity; c++) {
int profit1=0, profit2=0;
if(weights[i] <= c)
profit1 = profits[i] + dp[i][c-weights[i]];
if( i > 0 )
profit2 = dp[i-1][c];
dp[i][c] = profit1 > profit2 ? profit1 : profit2;
}
}
// maximum profit will be in the bottom-right corner.
return dp[n-1][capacity];
}
public static void main(String[] args) {
Knapsack ks = new Knapsack();
int[] profits = {15, 50, 60, 90};
int[] weights = {1, 3, 4, 5};
System.out.println(ks.solveKnapsack(profits, weights, 8));
System.out.println(ks.solveKnapsack(profits, weights, 6));
}
}
Самая длинная палиндромная подпоследовательность
Эта проблема:
Для данной последовательности найдите длину ее самой длинной палиндромной подпоследовательности (или LPS). В палиндромной подпоследовательности элементы читаются одинаково вперед и назад.
Подпоследовательность - это последовательность, которая может быть получена из другой последовательности путем удаления некоторых элементов или отсутствия каких-либо элементов без изменения порядка остальных элементов.
Пример 1:
Ввод: «abdbca»
Выход: 5
Пояснение: LPS - это «abdba».
Пример 2:
Ввод: = «cddpd»
Выход: 3
Пояснение: LPS - это «ддд».
Пример 3:
Ввод: = «pqr»
Выход: 1
Пояснение: LPS может быть «p», «q» или «r».
Простое решение:
Основное решение методом перебора может заключаться в том, чтобы попробовать все подпоследовательности данной последовательности. Мы можем начать обработку с начала и с конца последовательности. Итак, на любом этапе есть два варианта:
- Если элементы в начале и в конце совпадают, мы увеличиваем наш счет на два и делаем рекурсивный вызов для оставшейся последовательности.
- Мы можем пропустить элемент либо с начала, либо с конца, чтобы сделать два рекурсивных вызова для оставшейся подпоследовательности.
Если применяется первый вариант, он даст нам длину LPS. В противном случае длина LPS будет максимальным числом, возвращаемым двумя рекурсивными вызовами из второго варианта.
Вот код:
public class LPS {
public int findLPSLength(String st) {
return findLPSLengthRecursive(st, 0, st.length()-1);
}
private int findLPSLengthRecursive(String st, int startIndex, int endIndex) {
if(startIndex > endIndex)
return 0;
// every sequence with one element is a palindrome of length 1
if(startIndex == endIndex)
return 1;
// case 1: elements at the beginning and the end are the same
if(st.charAt(startIndex) == st.charAt(endIndex))
return 2 + findLPSLengthRecursive(st, startIndex+1, endIndex-1);
// case 2: skip one element either from the beginning or the end
int c1 = findLPSLengthRecursive(st, startIndex+1, endIndex);
int c2 = findLPSLengthRecursive(st, startIndex, endIndex-1);
return Math.max(c1, c2);
}
public static void main(String[] args) {
LPS lps = new LPS();
System.out.println(lps.findLPSLength(“abdbca”));
System.out.println(lps.findLPSLength(“cddpd”));
System.out.println(lps.findLPSLength(“pqr”));
}
}
Один подход DP: сверху вниз с мемоизацией
Мы можем использовать массив для хранения уже решенных подзадач.
Два изменяющихся значения нашей рекурсивной функции - это два индекса, startIndex и endIndex. Затем мы можем сохранить результаты всех подзадач в двумерном массиве.
Вот код:
public class LPS {
public int findLPSLength(String st) {
Integer[][] dp = new Integer[st.length()][st.length()];
return findLPSLengthRecursive(dp, st, 0, st.length()-1);
}
private int findLPSLengthRecursive(Integer[][] dp, String st, int startIndex, int endIndex) {
if(startIndex > endIndex)
return 0;
// every sequence with one element is a palindrome of length 1
if(startIndex == endIndex)
return 1;
if(dp[startIndex][endIndex] == null) {
// case 1: elements at the beginning and the end are the same
if(st.charAt(startIndex) == st.charAt(endIndex)) {
dp[startIndex][endIndex] = 2 + findLPSLengthRecursive(dp, st, startIndex+1, endIndex-1);
} else {
// case 2: skip one element either from the beginning or the end
int c1 = findLPSLengthRecursive(dp, st, startIndex+1, endIndex);
int c2 = findLPSLengthRecursive(dp, st, startIndex, endIndex-1);
dp[startIndex][endIndex] = Math.max(c1, c2);
}
}
return dp[startIndex][endIndex];
}
public static void main(String[] args) {
LPS lps = new LPS();
System.out.println(lps.findLPSLength(“abdbca”));
System.out.println(lps.findLPSLength(“cddpd”));
System.out.println(lps.findLPSLength(“pqr”));
}
}
Проблема Фибоначчи
Эта проблема:
Напишите функцию для вычисления n-го числа Фибоначчи.
Числа Фибоначчи - это ряд чисел, в которых каждое число является суммой двух предыдущих чисел. Первые несколько чисел Фибоначчи - это 0, 1, 2, 3, 5, 8 и так далее.
Мы можем определить числа Фибоначчи как:
Fib (n) = Fib (n-1) + Fib (n-2) для n ›1
Учитывая, что: Fib (0) = 0 и Fib (1) = 1
Основное решение:
Базовым решением может быть рекурсивная реализация приведенной выше математической формулы.
Вот код:
public class Fibonacci {
public int CalculateFibonacci(int n)
{
if(n < 2)
return n;
return CalculateFibonacci(n-1) + CalculateFibonacci(n-2);
}
public static void main(String[] args) {
Fibonacci fib = new Fibonacci();
System.out.println(fib.CalculateFibonacci(5));
System.out.println(fib.CalculateFibonacci(6));
}
}
Один подход DP: снизу вверх
Давайте попробуем заполнить наш массив «dp []» из приведенного выше решения, работая по восходящей схеме. Поскольку каждое число Фибоначчи является суммой двух предыдущих чисел, мы можем использовать этот факт для заполнения нашего массива.
Вот код для нашего подхода к динамическому программированию снизу вверх:
public class Fibonacci {
public int CalculateFibonacci(int n)
{
int dp[] = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i=2; i<=n; i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
public static void main(String[] args) {
Fibonacci fib = new Fibonacci();
System.out.println(fib.CalculateFibonacci(5));
System.out.println(fib.CalculateFibonacci(6));
System.out.println(fib.CalculateFibonacci(7));
}
}
Мы можем оптимизировать пространство, используемое в нашем предыдущем решении. Нам не нужно хранить все числа Фибоначчи вплоть до «n», поскольку нам нужны только два предыдущих числа для вычисления следующего числа Фибоначчи. Теперь мы можем еще больше улучшить наше решение:
public class Fibonacci {
public int CalculateFibonacci(int n)
{
int n1=0, n2=1, temp;
for(int i=2; i<=n; i++) {
temp = n1 + n2;
n1 = n2;
n2 = temp;
}
return n2;
}
public static void main(String[] args) {
Fibonacci fib = new Fibonacci();
System.out.println(fib.CalculateFibonacci(5));
System.out.println(fib.CalculateFibonacci(6));
System.out.println(fib.CalculateFibonacci(7));
}
}
Вышеупомянутое решение имеет временную сложность O (n), но постоянную пространственную сложность O (1).
Самая длинная общая подстрока
Эта проблема:
Для двух строк «s1» и «s2» найдите длину самой длинной подстроки, общей в обеих строках.
Пример 1:
Ввод: s1 = «abdca»
s2 = «cbda»
Выход: 2
Объяснение: Самая длинная общая подстрока - «bd».
Пример 2:
Ввод: s1 = «паспорт»
s2 = «ppsspt»
Выход: 3
Объяснение: Самая длинная общая подстрока - «ssp».
Простое решение:
Основное решение методом перебора может заключаться в том, чтобы попробовать все подстроки «s1» и «s2», чтобы найти самую длинную из общих. Мы можем начать сопоставление обеих строк по одному символу за раз, поэтому у нас есть два варианта на любом этапе:
- Если строки имеют совпадающий символ, мы можем рекурсивно сопоставить оставшуюся длину и отслеживать текущую совпадающую длину.
- Если строки не совпадают, мы можем начать два новых рекурсивных вызова, пропуская один символ отдельно от каждой строки.
Длина самой длинной общей подстроки (LCS) будет максимальным числом, возвращаемым тремя рекурсивными вызовами в двух вышеупомянутых вариантах.
Вот код:
public class LCS {
public int findLCSLength(String s1, String s2) {
return findLCSLengthRecursive(s1, s2, 0, 0, 0);
}
private int findLCSLengthRecursive(String s1, String s2, int i1, int i2, int count) {
if(i1 == s1.length() || i2 == s2.length())
return count;
if(s1.charAt(i1) == s2.charAt(i2))
count = findLCSLengthRecursive(s1, s2, i1+1, i2+1, count+1);
int c1 = findLCSLengthRecursive(s1, s2, i1, i2+1, 0);
int c2 = findLCSLengthRecursive(s1, s2, i1+1, i2, 0);
return Math.max(count, Math.max(c1, c2));
}
public static void main(String[] args) {
LCS lcs = new LCS();
System.out.println(lcs.findLCSLength(“abdca”, “cbda”));
System.out.println(lcs.findLCSLength(“passport”, “ppsspt”));
}
}
Временная сложность описанного выше алгоритма экспоненциальна O (2 ^ (m + n)), где «m» и «n» - длины двух входных строк. Сложность пространства O (n + m), это пространство будет использоваться для хранения стека рекурсии.
Один подход DP: сверху вниз с мемоизацией
Мы можем использовать массив для хранения уже решенных подзадач.
Три изменяющихся значения нашей рекурсивной функции - это два индекса (i1 и i2) и «count». Следовательно, мы можем хранить результаты всех подзадач в трехмерном массиве. (Другой альтернативой может быть использование хеш-таблицы, ключ которой будет строкой (i1 + «-» i2 + «-» + count)).
Вот код:
public class LCS {
public int findLCSLength(String s1, String s2) {
int maxLength = Math.max(s1.length(), s2.length());
Integer[][][] dp = new Integer[s1.length()][s2.length()][maxLength];
return findLCSLengthRecursive(dp, s1, s2, 0, 0, 0);
}
private int findLCSLengthRecursive(Integer[][][] dp, String s1, String s2, int i1, int i2, int count) {
if(i1 == s1.length() || i2 == s2.length())
return count;
if(dp[i1][i2][count] == null) {
int c1 = count;
if(s1.charAt(i1) == s2.charAt(i2))
c1 = findLCSLengthRecursive(dp, s1, s2, i1+1, i2+1, count+1);
int c2 = findLCSLengthRecursive(dp, s1, s2, i1, i2+1, 0);
int c3 = findLCSLengthRecursive(dp, s1, s2, i1+1, i2, 0);
dp[i1][i2][count] = Math.max(c1, Math.max(c2, c3));
}
return dp[i1][i2][count];
}
public static void main(String[] args) {
LCS lcs = new LCS();
System.out.println(lcs.findLCSLength(“abdca”, “cbda”));
System.out.println(lcs.findLCSLength(“passport”, “ppsspt”));
}
}
Самая длинная общая подпоследовательность:
Эта проблема:
Для двух строк «s1» и «s2» найдите длину самой длинной подпоследовательности, которая является общей для обеих строк.
Пример 1:
Ввод: s1 = «abdca»
s2 = «cbda»
Выход: 3
Объяснение: Самая длинная подстрока - «bda».
Пример 2:
Ввод: s1 = «паспорт»
s2 = «ppsspt»
Выход: 5
Объяснение: Самая длинная подстрока - «psspt».
Простое решение:
Основное решение методом перебора может заключаться в том, чтобы попробовать все подпоследовательности «s1» и «s2», чтобы найти самую длинную. Мы можем сопоставить обе строки по одному символу за раз. Таким образом, для каждого индекса «i» в «s1» и «j» в «s2» мы должны выбирать между:
- Если символ «s1 [i]» совпадает с «s2 [j]», мы можем рекурсивно сопоставить оставшуюся длину.
- Если символ «s1 [i]» не соответствует «s2 [j]», мы начнем два новых рекурсивных вызова, пропуская один символ отдельно от каждой строки.
Вот код:
public class LCS {
public int findLCSLength(String s1, String s2) {
return findLCSLengthRecursive(s1, s2, 0, 0);
}
private int findLCSLengthRecursive(String s1, String s2, int i1, int i2) {
if(i1 == s1.length() || i2 == s2.length())
return 0;
if(s1.charAt(i1) == s2.charAt(i2))
return 1 + findLCSLengthRecursive(s1, s2, i1+1, i2+1);
int c1 = findLCSLengthRecursive(s1, s2, i1, i2+1);
int c2 = findLCSLengthRecursive(s1, s2, i1+1, i2);
return Math.max(c1, c2);
}
public static void main(String[] args) {
LCS lcs = new LCS();
System.out.println(lcs.findLCSLength(“abdca”, “cbda”));
System.out.println(lcs.findLCSLength(“passport”, “ppsspt”));
}
}
Один подход DP: снизу вверх
Поскольку мы хотим сопоставить все подпоследовательности данных двух строк, мы можем использовать двумерный массив для хранения наших результатов. Длина двух строк будет определять размер двух измерений массива. Таким образом, для каждого индекса «i» в строке «s1» и «j» в строке «s2» мы можем выбрать один из этих двух вариантов:
- Если символ s1 [i] соответствует s2 [j], длина общей подпоследовательности будет равна единице плюс длина общей подпоследовательности до индексов «i-1» и «j-1» в двух соответствующих строках.
- Если символ s1 [i] не соответствует s2 [j], мы возьмем самую длинную подпоследовательность, пропустив i-й или j-й символ из соответствующих строк.
Итак, наша рекурсивная формула будет такой:
if si[i] == s2[j]
dp[i][j] = 1 + dp[i-1][j-1]
еще
dp [i] [j] = max (dp [i-1) [j], dp [i] [j-1] »)
Вот код:
public class LCS {
public int findLCSLength(String s1, String s2) {
int[][] dp = new int[s1.length()+1][s2.length()+1];
int maxLength = 0;
for(int i=1; i <= s1.length(); i++) {
for(int j=1; j <= s2.length(); j++) {
if(s1.charAt(i-1) == s2.charAt(j-1))
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
maxLength = Math.max(maxLength, dp[i][j]);
}
}
return maxLength;
}
public static void main(String[] args) {
LCS lcs = new LCS();
System.out.println(lcs.findLCSLength(“abdca”, “cbda”));
System.out.println(lcs.findLCSLength(“passport”, “ppsspt”));
}
}
Сложность описанного выше алгоритма по времени и пространству составляет O (m * n), где «m» и «n» - длины двух входных строк.
Продолжай учиться!
Это лишь небольшой пример концепций динамического программирования и проблем, с которыми вы можете столкнуться на собеседовании по кодированию.
Для получения дополнительной практики, включая еще десятки проблем и решений для каждого шаблона, ознакомьтесь с Grokking Dynamic Programming Patterns for Coding Interviews на сайте Educative.
Первоначально опубликовано на blog.educative.io 15 января 2019 г.
