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

Динамическое программирование — это полная форма (аббревиатура DP), известная как наиболее сложная техника решения проблем. Этот метод в основном используется для задач оптимизации и задач подсчета. Если вы столкнулись с проблемой, в которой говорится «минимизируй это», «максимизируй это» или «подсчитай способы сделать это», то есть большая вероятность, что это проблема DP. Теперь предположим, что вам дано такое проблемное состояние:

Проблема 1: Дана сетка M*N. и вы можете двигаться вниз, прямо в ячейках сетки. Ваша начальная позиция — верхний левый угол сетки. Таким образом, вы должны сказать, сколько существует способов попасть в нижний правый угол сетки.

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

Каковы предварительные условия для работы с этой статьей?

Вы должны быть знакомы с рекурсией и рекуррентными отношениями и уметь решать проблемы рекурсивного возврата. На самом деле, проблемы DP с небольшими входными ограничениями уже могут быть решены с помощью рекурсивного поиска с возвратом. Таким образом, можно предположить, что DP (подход сверху вниз) является своего рода «интеллектуальным» или «более быстрым» рекурсивным возвратом. Существует два способа решения задач ДП: 1. Подход «сверху вниз»; 2. Восходящий подход. Эта статья (часть 1) посвящена DP (нисходящему подходу).

Цели этой статьи:

1. Устраните путаницу, чтобы определить, является ли это проблемой DP или нет.

2. Пройдите через различные типы проблем DP.

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

4. Определите временную и пространственную сложность рекурсивного поиска с возвратом и метода DP.

Давайте углубимся в проблему, чтобы достичь целей этой статьи.

Сначала подумайте о проблеме номер 1. Где вам дана сетка M*N. Вы должны сказать, сколько существует способов попасть в правый нижний угол. Тривиально мы можем написать эту функцию, где x, y — положение путешественника, а M, N — размер сетки, который должен быть передан в аргументе функции в базовый случай.

базовый случай

если(x==M-1 && y==N-1) вернуть 1;

public static int numberOfTravels(int x, int y, int M, int N)
{
    // validate position
    if(x<0 || x>M || y<0 || y>N) return 0;
    //base case
    if(x == M-1 && y == N-1) return 1;
            // number of way if Traveler (go right + go down)
    return (numberOfTravels(x, y+1, M,N) + numberOfTravels(x+1,y,M,N));
}

Давайте посмотрим на проблему с другой точки зрения. Если вам дана сетка 1 * 1, результат будет один. итак, чтобы идти вниз: индекс позиции будет x-1,y и идти вправо: x,y-1; и рекурсивно вы столкнетесь с позициями x == 1 и y == 1, что является базовым случаем.

public static int numberOfTravels(int x, int y)
{
    // validate position
    if(x<=0 || y<=0) return 0;
    // base case
    if(x == 1 && y == 1) return 1;
    return (numberOfTravels(x, y-1) + numberOfTravels(x-1, y));
}

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

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

Каковы основные шаги для решения проблемы DP в подходе «сверху вниз»:

  1. Сделай так, чтоб это работало
  • Визуализируйте проблему в виде дерева.
  • Реализовать дерево с помощью рекурсии
  • Попробуй это.

2. Сделайте его эффективным

  • чтобы добавить мемо-объект/массив в функцию
  • и добавьте базовый вариант для возврата значений памятки.
  • сохранить возвращаемые значения в памятку
public static int numberOfTravels(int x, int y, int[][] memo)
{
    // validate position
    if(x<=0 || y<=0) return 0;
    // base case
    if(x == 1 && y == 1) return 1;
    if(memo[x][y]!=-1) return memo[x][y];
    return memo[x][y] = (numberOfTravels(x, y-1, memo) + numberOfTravels(x-1, y, memo));
}

Теперь вы можете решить следующие проблемы ??

Проблема 2: Напишите функцию CanSum(targetSum, numbers); функция должна возвращать логическое значение, указывающее, возможно ли сгенерировать targetSum, используя числа из массива. Гдеэлемент массива может использоваться столько раз, сколько необходимо, а элементы неотрицательны.

Постановка задачи 3. Напишите функцию HowSum(targetSum, numbers); Функция должна возвращать массив, содержащий любую комбинацию элементов, которая в сумме точно равна targetSum. Если комбинации нет, верните null. Если возможно несколько комбинаций, вы можете вернуть любую из них.

Постановка задачи 4: То же, что и постановка задачи 3, но теперь нужно найти кратчайшую комбинацию чисел, которая в сумме дает точно заданную сумму.

Постановка задачи 5. Напишите функцию canConstruct(target, wordBank), которая принимает целевую строку и массив строк. Функция должна возвращать логическое значение, указывающее, можно ли создать цель путем объединения элементов массива wordBank. Вы можете повторно использовать элементы wordBank столько раз, сколько необходимо.

Постановка задачи 6. Напишите функцию countConstruct(target, wordBank), которая принимает целевую строку и массив строк. Функция должна возвращать количество способов, которыми цель может быть создана путем объединения элементов массива wordBank. Вы можете повторно использовать элементы wordBank столько раз, сколько необходимо.

Постановка задачи 7. Напишите функцию allConstruct(target, wordBank), которая принимает целевую строку и массив строк. Функция должна возвращать двумерный массив, содержащий все способы построения цели путем объединения элементов массива wordBank. Вы можете повторно использовать элементы wordBank столько раз, сколько необходимо.

Некоторые другие фундаментальные проблемы.

  1. Вычислите 40-е число последовательности Фибоначчи.
  2. Подсчитайте количество различных способов перемещения по сетке 6*9.
  3. Учитывая набор монет, как мы можем заработать 27 центов за наименьшее количество монет?
  4. Какими способами можно составить строку «potentpot» для заданного набора подстрок?

Если вам понравилась эта статья, нажмите несколько раз кнопку "хлопать" 👏.

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

Подпишитесь на меня Маахи, чтобы получать мои еженедельные статьи.

Следите за моим Блогом, где мы обсуждаем структуры данных и алгоритмы.

Спасибо, что прочитали.

Приятного обучения! 😁