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

Вот блестящее объяснение концепции динамического программирования на Quora Ответ Джонатана Полсона на вопрос Как мне объяснить динамическое программирование 4-летнему ребенку?

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

  1. Самая длинная общая подпоследовательность | Введение и длина LCS
  2. Самая длинная общая подпоследовательность | Поиск всех LCS
  3. Проблема с самой длинной общей подстрокой
  4. Самая длинная палиндромная подпоследовательность с использованием динамического программирования
  5. Проблема самой длинной повторяющейся подпоследовательности
  6. Внедрить Diff Utility
  7. Кратчайшая общая суперпоследовательность | Введение и длина SCS
  8. Кратчайшая общая суперпоследовательность | Поиск всех СКС
  9. Самая длинная возрастающая подпоследовательность с использованием динамического программирования
  10. Самая длинная битоническая подпоследовательность
  11. Увеличение подпоследовательности с максимальной суммой
  12. Задача о расстоянии Левенштейна (Редактировать расстояние)
  13. Найти размер наибольшей квадратной подматрицы единиц, присутствующей в данной двоичной матрице
  14. Умножение цепочки матриц с использованием динамического программирования
  15. Найти минимальную стоимость достижения последней ячейки матрицы от ее первой ячейки
  16. Найти самую длинную последовательность, образованную соседними числами в матрице
  17. Подсчитать количество путей в матрице с заданной стоимостью для достижения ячейки назначения
  18. 0–1 Задача о ранце
  19. Максимизируйте ценность выражения
  20. Проблема раздела | Решение для динамического программирования
  21. Проблема суммы подмножества
  22. Задача о разделении минимальной суммы
  23. Найти все N-значные двоичные строки без последовательных единиц
  24. Проблема резки стержня
  25. Максимальная резка прутка продукта
  26. Проблема обмена монет (неограниченное количество монет)
  27. Проблема обмена монет (Общее количество способов узнать номинал монет)
  28. Задача самой длинной чередующейся подпоследовательности
  29. Подсчитать, сколько раз шаблон встречается в данной строке как подпоследовательность
  30. Набрать максимальное количество очков в матрице, удовлетворяя заданным ограничениям
  31. Подсчитайте общее количество возможных комбинаций N-значных чисел в мобильной клавиатуре
  32. Найдите оптимальную стоимость для построения двоичного дерева поиска
  33. Проблема с разрывом слова | Динамическое программирование
  34. Проблема с разрывом слова | Использование структуры данных Trie
  35. Суммарные возможные решения линейного уравнения k переменных
  36. Соответствие шаблону подстановочного знака
  37. Найти вероятность того, что человек жив после N шагов на острове
  38. Вычислить сумму всех элементов в подматрице за постоянное время
  39. Найти подматрицу максимальной суммы в заданной матрице
  40. Найти подматрицу максимальной суммы, присутствующую в данной матрице
  41. Найти максимальную сумму подпоследовательности без смежных элементов
  42. Задача о максимальном подмассиве (алгоритм Кадане)
  43. Кратчайшие пути от одного источника - алгоритм Беллмана-Форда
  44. Кратчайшие пути для всех пар - алгоритм Флойда Уоршалла
  45. Игра в горшки с золотом с использованием динамического программирования
  46. Найдите минимальные разрезы, необходимые для палиндромного разделения струны
  47. Змейка максимальной длины
  48. Проблема с 3 разделами
  49. Вычислить размер наибольшего плюс 1 в двоичной матрице
  50. Проверить, чередуется ли данная строка с двумя другими заданными строками