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

Шаг 0: Выявление проблем динамического программирования.

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

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

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

Шаг 1: понимание, по какому пути вам следует идти, чтобы решить проблему.

Давайте немного проясним то, что я сказал выше: если вы достаточно хорошо поняли основы динамического программирования, начните рисовать шаблоны, формулируя эти основные вопросы; если нет, то идите и решите вопросы или внимательно прочитайте эти вопросы, чтобы максимально эффективно использовать эти вопросы. Я рекомендую продолжать спрашивать, почему решение привело к определенному результату.

Вопросы:

  • 0/1 Рюкзак и неограниченный рюкзак
  • кратчайший путь
  • поиск подпоследовательностей и/или самой длинной общей подстроки
  • Алгоритм покраски забора
  • проблема с нарезкой стержня
  • Умножение цепочки матриц

Большинство проблем будут вариациями некоторых из вышеперечисленных вопросов. НЕ ТО ЖЕ, но может использовать аналогичный подход, который поможет вам понять, что происходит.

Шаг 1 а. написание решения грубой силы:

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

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

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

Здесь я использую пример сегментов разрезанного стержня:

int solve(int n, int x, int y, int z) {
  if (n == 0) { //base condition
	  return 0; 
  }
  if (n < 0) { //base condition
	  return INT_MIN; 
  }
  int a = solve(n-x, x,y,z)+1; //considering x length cut
  int b = solve(n-y,x,y,z)+1; //considering y length cut
  int c = solve(n-z,x,y,z)+1;//considering z length cut
  int ans = max(a, max(b,c)); //finding the maximum out of the three. 
  return ans; //returning the answer.
}

Шаг 2: определение того, какое состояние обновляется в вашем рекурсивном решении.

→ Это важный шаг, чтобы понять, какая структура данных Dp и будет ли эта динамическая проблема 1-D dp или 2-D dp.

Понимание того, какое состояние обновляется в вашем рекурсивном решении, имеет решающее значение. Это поможет вам решить, использовать ли подход к динамическому программированию 1D или 2D. В приведенном выше фрагменте мы обновляем только «n», указывая на одномерную структуру данных.

vector<int> dp(n+1, -1);

НО для тех, кто не любит кодировать на C++, мы создали динамический массив размером n+1 и предварительно заполнили все элементы как -1.

ПОЧЕМУ n+1?

→ +1: потому что наша индексация начинается с 0, а не с 1.

→ n: потому что это состояние, которое нас больше всего беспокоит и которое мы отслеживаем.

→ -1: Установив начальное значение каждого элемента массива DP равным -1, мы указываем, что эти значения еще не рассчитаны. Поскольку отрицательные длины не имеют отношения к контексту нашей задачи, это значение не будет обновляться во время решения, что позволяет нам легко различать вычисляемые и невычисленные состояния.

Это помогает нам понять, ПОЧЕМУ мы делаем определенные вещи.

Шаг 3: преобразование рекурсивного решения в решение для мемоизации.

→ Решения динамического программирования позволяют систематически отслеживать принятые и ожидаемые решения. Начальное значение «-1» означает, что решения еще не приняты. По мере продвижения решения эти значения обновляются, чтобы указать, что решения были приняты и соответствующие результаты записаны.

→ ПРИМЕЧАНИЕ. Я собираюсь порекомендовать следовать методу, который требует от вас просто слепо следовать тому, что я вам говорю, но вы должны быть более осознанными по мере того, как больше практикуетесь.

  1. передайте массив dp в ваш рекурсивный вызов функции. :
  2. Базовые условия остаются прежними, но нам нужно добавить еще одно базовое условие: если вы догадались, проверяя решение dp[index], то вы правы.
if (n == 0) { //base condition
	  return 0; 
  }
  if (n < 0) { //base condition
	  return INT_MIN; 
  }
	if(dp[n]!=-1){ //check if it's already been updated.
	  return dp[n];
  }
  1. Помните, что вам нужно обновить значение dp[index], поэтому вам нужно вернуть это значение вместо «ans».
int a = solve(n-x, x,y,z)+1; //considering x length cut
  int b = solve(n-y,x,y,z)+1; //considering y length cut
  int c = solve(n-z,x,y,z)+1;//considering z lenghth cut
  int ans = max(a, max(b,c)); //finding the maximum out of the three. 
  return ans; //returning the answer.
int a = solveMem(n-x, x,y,z,dp)+1;
  int b = solveMem(n-y,x,y,z,dp)+1;
  int c = solveMem(n-z,x,y,z,dp)+1;
  dp[n] = max(a, max(b,c));
  return dp[n];

сохранение их рядом будет иметь гораздо больше смысла.

  1. и вуаля, у вас есть запомненное решение Dp.

Шаг 4: преобразование запомненного решения в табличный метод (снизу вверх).

→ Для решения проблемы табличному методу также потребуется массив dp, но мы подходим иначе.

Мы не передаем массив dp в качестве одного из аргументов при вызове функции.

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

int solveTab(int n, int x, int y, int z) {
  
  vector<int> dp(n+1,INT_MIN);
 }

→ Посмотрите на базовые условия и попытайтесь сохранить значения в массиве dp.

что я имею в виду:

if (n == 0) { //base condition
	  return 0; 
  }
dp[0]= 0;

→ Мы знали, что когда мы достигаем 0-го индекса, нам нужно сохранить 0.

→ А как насчет другого базового состояния? ну, мы решили это в предварительно заполненном значении.

→ Следующее, что мы будем делать, это преобразовать рекурсивное решение в итеративное решение. Поэтому очевидно, что вместо этого мы будем использовать циклы for.

for (int i = 1; i <=n; i++) { //this is mimicking the recursive solution iterations from 1 to n
	if(i-x>=0) //in case we run out of bounds we put a check
		dp[i] = max(dp[i],dp[i-x]+1); 
        if(i-y>=0)
		dp[i] = max(dp[i],dp[i-y]+1); 
        if(i-z>=0)
		dp[i] = max(dp[i],dp[i-z]+1); 
	  
  }

→ Последний шаг — вернуть соответствующий ответ.

if(dp[n]<0){ //it means it was never achieved, as you remember from the initation 
	  return 0; 
}
else
	  return dp[n]; 
}

И вы успешно написали табличное решение. Теперь вам нужно использовать тот же метод для каждого решения, чтобы записать решения.

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

Шаг 5: оптимизация пространства.

→ если вы заметили, что мы все еще потребляем O(n) пространство для решения этой проблемы, что не всегда является лучшим решением. Итак, нам нужно посмотреть, сможем ли мы решить эту задачу в пространстве O(1).

→ К сожалению, мы не сможем найти решение в пространстве O(1), по крайней мере, я не смог, но я все равно расскажу вам процесс.

→ посмотрите внимательно на звонки:

dp[i] = max(dp[i],dp[i-x]+1);

мы могли бы оптимизировать их, если бы знали, каким будет значение dp[i-x]. скажем, это предыдущее значение.

Другими словами, dp[i] зависел от dp[i-1] и/или dp[i-2] ; В этой ситуации мы знали, что простое отслеживание двух предыдущих значений поможет нам решить проблему и вместо этого избавиться от массива dp.

Хотя достижение пространства O(1) обычно невозможно, понимание этой концепции имеет важное значение. Проанализируйте зависимости в своем решении и подумайте, можно ли оптимизировать использование памяти, отслеживая меньшее количество значений.

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

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

Приятного решения проблем!