9. Динамическое программирование. Одномерная динамика "Зайчик". Двумерная динамика "Черепашка".

1. Динамическое программирование.

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

Суть метода в следующем: имеющуюся задачу рекурсивно разбиваем на более маленькие подзадачи, их — на ещё меньшие и так далее. Но решаем задачи в обратном порядке: сначала маленькие (запоминаем их решение), потом переходим к задачам побольше (строим их решение на основе сохранённых решений маленьких задач) и так далее, пока не решим исходную большую задачу.

Преимущества метода:

• за счёт запоминания решения промежуточных подзадач мы каждую такую подзадачу решаем только один раз, т.е. экономим время;
• избавляемся от рекурсии (заменяем её на вложенные циклы).

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

Обычно динамическое программирование применяют в задачах, связанных с оптимизацией, например, когда нужно найти кратчайший маршрут для перемещения из города A в город B. Либо это могут быть задачи, где нужно просчитать все возможные комбинации переходов или расположения элементов. Классический пример, в котором используется этот метод — последовательность чисел Фибоначчи:
F(n) = F(n-1) + F(n-2);
F(0)=0;
F(1)=F(2)=1;

2. Одномерная динамика. «Зайчик».

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. То есть при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

Входные данные:

Два натуральных числа K и N (1 ≤ K ≤ N ≤ 300). К — максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.

Выходные данные:

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

Суть динамического программирования как раз состоит в том, что мы:

• разбиваем сложную задачу на более простые — делать это можем как с использованием рекурсии, так и без нее;
• используем мемоизацию результатов вычислений (накапливаем их и используем вместо повторного вычисления).

Фрагмент кода программы:

Console.Write("Введите k:");
int k = Convert.ToInt32(Console.ReadLine());
Console.Write("Введите n:");
int n = Convert.ToInt32(Console.ReadLine());
n++;
ulong[] counts = new ulong[n];
counts[0] = 1;
for (int i = 1; i < n; i++)
{
    int min = k;
    if (i < k)
    {
        min = i;
    }

    for (int j = 1; j <= min; j++)
    {
        counts[i] += counts[i - j];
    }
}

Console.WriteLine("Ответ:" + counts[n - 1]);

Приведенный выше код совершенно правильный и достаточно быстрый, однако решение не пройдет, ведь в результате могут получаться огромные числа, так, например, для максимально допустимых в условии задачи значений параметров k и n ответ должен быть таким:

1018517988167243043134222844204689080525734196832968125318070224677190649881668353091698688

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

Но это уже другая история…

3. Двумерная динамика. «Черепашка».

Дано прямоугольное поле размером n*m клеток. Черепашка может совершать шаги длиной только в одну клетку вправо или вниз. В каждой клетке записано некоторое натуральное число – масса растений в этой клетке. Черепашке очень надо попасть из верхней левой клетки в правую нижнюю. Но она никуда не спешит, и поэтому хочет съесть как можно большую суммарную массу растений. Необходимо узнать общий вес травы, съеденной черепашкой при движении по маршруту с максимальным весом (вес маршрута вычисляется как сумма чисел со всех посещенных клеток).

Фрагмент кода программы:

private static int[,] _array =
{
    {1, 3, 1, 2},
    {5, 1, 2, 3},
    {6, 4, 5, 6},
    {2, 2, 1, 7},
    {1, 10, 11, 2}
};

private static int[,] _turtle = new int[_array.GetLength(0), _array.GetLength(1)];

public static void Main(string[] args)
{
    int n = _array.GetLength(0);
    int m = _array.GetLength(1);

    _turtle[0, 0] = _array[0, 0];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int up = 0;
            if (i > 0)
            {
                up = _turtle[i - 1, j];
            }

            int left = 0;
            if (j > 0)
            {
                left = _turtle[i, j - 1];
            }

            if (up > left)
            {
                _turtle[i, j] = up + _array[i, j];
            }
            else
            {
                _turtle[i, j] = left + _array[i, j];
            }
        }
    }

    Print(_array);
    Print(_turtle);

    Console.WriteLine("Ответ:" + _turtle[n-1, m-1]);
}

private static void Print(int[,] array)
{
    for (int i = 0; i < array.GetLength(0); i++)
    {
        for (int j = 0; j < array.GetLength(1); j++)
        {
            Console.Write(quot;{array[i, j]} \t");
        }

        Console.WriteLine();
    }

    Console.WriteLine();
}

Задание: Попробуйте самостоятельно вывести на экран маршрут с максимальным весом для черепашки (если таких маршрутов несколько, можно вывести любой). Маршрут представляет собой последовательное перечисление координат всех клеток, посещаемых черепашкой. Координаты клетки – ее номер строки и столбца в двумерном массиве.

Итоги занятия.