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

Дана последовательность из n матриц заданных размеров [A₁, A₂, ..., A_n] (матрица A_i имеет размер p_i-1 на p_i ); требуется найти такую (полную) расстановку скобок в произведении A₁A₂ ... A_n, чтобы вычисление произведения требовало наименьшего числа умножений и найти результат перемножения этих матриц. [1, с.289].
Комментарии вы можете посмотреть на 7 шаге.
Решение вы можете посмотреть здесь.
    В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от неё. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остаётся только две карты.
    Цель игры - убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.
    Ограничения: 3 ≤ N ≤ 50, числа на картах целые от 1 до 50, время 1с. [2].
Комментарии вы можете посмотреть на 8 шаге.
Решение вы можете посмотреть здесь.
Найдите общую подпоследовательность наибольшей длины для двух данных последовательностей. [1, с.300].
Комментарии вы можете посмотреть на 9 шаге.
Решение вы можете посмотреть здесь.
В таблице размером N*N, где N<13, клетки заполнены случайным образом цифрами от 0 до 9. Предложить Чебурашке алгоритм, позволяющий найти маршрут из клетки (1, 1) в клетку (N, N) и удовлетворяющий следующим условиям:
- любые две последовательные клетки в маршруте имеют общую сторону;
- количество клеток маршрута минимально;
- сумма цифр в клетках маршрута максимальна. [3].
Комментарии вы можете посмотреть на 10 шаге.
Решение вы можете посмотреть здесь.
    Дана матрица N*N, заполненная положительными числами. Путь по матрице начинается в левом верхнем углу. За один ход можно пройти в соседнюю по вертикали или горизонтали клетку (если она существует). Нельзя ходить по диагонали, нельзя оставаться на месте. Требуется найти максимальную сумму чисел, стоящих в клетках по пути длиной K (клетку можно посещать несколько раз).
    Ограничения: 2 ≤ N ≤ 15, элементы матрицы имеют значения от 1 до 999, 1 ≤ K ≤ 20, все числа целые, время 5с.
    Ввод из файла route2.in. В первой строке находятся разделенные пробелом числа N и K. Затем идут N строк по N чисел в каждой.
    Вывод в файл route2.out. Вывести одно число - максимальную сумму. [2].
Комментарии вы можете посмотреть на 11 шаге.
Решение вы можете посмотреть здесь.
Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность P_i и вес W_i одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
Ограничения: 1 ≤ E ≤ F ≤ 100, 1 ≤ N ≤ 50, 1 ≤ P_i ≤ 500, 1 ≤ W_i ≤ 100, все числа целые, время 2с. [2].
Комментарии вы можете посмотреть на 12 шаге.
Решение вы можете посмотреть здесь.

⁽¹⁾Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2000.-960с.,263 ил.
⁽²⁾Меньшиков Ф.В. Олимпиадные задачи по программированию. - СПб: Питер, 2006. - 315с.
⁽³⁾Статья "Динамическое программирование и жадные алгоритмы"
(http://kitnet.altnet.ru/www/metod/book3/doc1/str1.htm)

На следующем шаге мы разберем решение задачи "Перемножение нескольких матриц".

Предыдущий шаг Содержание Следующий шаг