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

Варианты заданий

1. Дана матрица A размером n×m с целыми числами, по модулю не превосходящими 1000. Разработать динамический алгоритм, который находит количество подматриц матрицы A, сумма элементов которых в точности равна заданному числу S.
   Например: в матрице размером 3 × 3, состоящей из единиц, количество подматриц размера 2 × 2 с суммой элементов 4 равно 4.

2. Дана матрица A размером n×m с целыми числами, по модулю не превосходящими 1000. Разработать динамический алгоритм, который находит квадратную подматрицу с максимальной суммой элементов.

3. Дано натуральное число n (n кубиков). Лесенка — это набор из ступенек, размер которых уменьшается снизу вверх. Лесенка состоит по крайней мере из двух ступенек, ступенька состоит, по крайней мере, из одного кубика.
   Например: лесенка из 3 кубиков представляет собой первую ступеньку из двух кубиков и вторую ступеньку из одного.
   Необходимо разработать алгоритм, подсчитывающий количество лесенок, которые можно составить из n кубиков.

4. Дана прямоугольная таблица (n строк, m столбцов), в клетках которой записаны целые числа. Черепашка находится в левой нижней клетке, и ей необходимо попасть в правую верхнюю клетку. Количество способов достижения конечной клетки при размере таблицы n × m равно С^n-1_n+m-2. Черепашке разрешено двигаться вверх и вправо, а также по диагонали (на одну клетку). Разработать алгоритм, подсчитывающий количество способов достижения Черепашкой конечной клетки.

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

6. Даны два натуральных числа n и k. Вычисляется kⁿ. Разрешается использовать операции умножения и возведения в степень, круглые скобки и переменную с именем k. Умножение считается одной операцией, возведению в степень q соответствует q–1 операция.
   Необходимо разработать алгоритм, определяющий минимальное количество операций, необходимых для возведения k в степень n. Желательно сделать это для как можно больших значений n.
   Например: при n = 5 необходимы три операции: (k× k)²× k.

7. На столе находится n спичек, и два игрока по очереди берут спички из кучки. Первому игроку разрешается взять от 1 до k спичек. А затем игроки могут брать любое количество спичек, но не более чем на 1 превышающее то количество, которое взял игрок перед ним (можно взять меньше или столько же, но обязательно хотя бы одну). Проигрывает тот, кто возьмет последнюю спичку.
   Например: Пусть n = 10 и k = 5. На первом ходу первый игрок может взять 1, 2, 3, 4 или 5 спичек. Если первый игрок возьмет 3 спички, то на следующем ходу второй игрок может взять 1, 2, 3 или 4 спички. А если первый игрок возьмет одну спичку, то второй затем может взять 1 или 2 спички.

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

8. Палиндром — это симметричная строка, то есть она одинаково читается как слева направо, так и справа налево. Требуется разработать алгоритм, определяющий по заданной строке минимальное количество символов, которые необходимо вставить в строку для преобразования её в палиндром.
   Входные данные представляют собой строку длиной n, которая состоит из прописных (заглавных) букв от «A» до «Z», строчных букв от «a» до «z» и цифр от «0» до «9». Прописные и строчные буквы считаются различными. Результатом является одно целое число — минимальное количество вставляемых символов.
   Пример. Путем вставки двух символов строка «Ab3bd» может быть преобразована в палиндром («dAb3bAd» или «Adb3bdA»), а вставкой менее двух символов палиндром в этом примере получить нельзя.

9. Дана матрица A размером n×m с целыми числами, по модулю не превосходящими 1000. Разработать динамический алгоритм, который находит количество подматриц матрицы A, сумма элементов которых в точности равна заданному числу S.
   Например: в матрице размером 3 × 3, состоящей из единиц, количество подматриц размера 2 × 2 с суммой элементов 4 равно 4.

10. Дана матрица A размером n×m с целыми числами, по модулю не превосходящими 1000. Разработать динамический алгоритм, который находит квадратную подматрицу с максимальной суммой элементов.

11. Дано натуральное число n (n кубиков). Лесенка — это набор из ступенек, размер которых уменьшается снизу вверх. Лесенка состоит по крайней мере из двух ступенек, ступенька состоит, по крайней мере, из одного кубика.
    Например: лесенка из 3 кубиков представляет собой первую ступеньку из двух кубиков и вторую ступеньку из одного.
    Необходимо разработать алгоритм, подсчитывающий количество лесенок, которые можно составить из n кубиков.

12. Дана прямоугольная таблица (n строк, m столбцов), в клетках которой записаны целые числа. Черепашка находится в левой нижней клетке, и ей необходимо попасть в правую верхнюю клетку. Количество способов достижения конечной клетки при размере таблицы n × m равно С^n-1_n+m-2. Черепашке разрешено двигаться вверх и вправо, а также по диагонали (на одну клетку). Разработать алгоритм, подсчитывающий количество способов достижения Черепашкой конечной клетки.

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

14. Даны два натуральных числа n и k. Вычисляется kⁿ. Разрешается использовать операции умножения и возведения в степень, круглые скобки и переменную с именем k. Умножение считается одной операцией, возведению в степень q соответствует q–1 операция.
    Необходимо разработать алгоритм, определяющий минимальное количество операций, необходимых для возведения k в степень n. Желательно сделать это для как можно больших значений n.
    Например: при n = 5 необходимы три операции: (k× k)²× k.

15. На столе находится n спичек, и два игрока по очереди берут спички из кучки. Первому игроку разрешается взять от 1 до k спичек. А затем игроки могут брать любое количество спичек, но не более чем на 1 превышающее то количество, которое взял игрок перед ним (можно взять меньше или столько же, но обязательно хотя бы одну). Проигрывает тот, кто возьмет последнюю спичку.
    Например: Пусть n = 10 и k = 5. На первом ходу первый игрок может взять 1, 2, 3, 4 или 5 спичек. Если первый игрок возьмет 3 спички, то на следующем ходу второй игрок может взять 1, 2, 3 или 4 спички. А если первый игрок возьмет одну спичку, то второй затем может взять 1 или 2 спички.

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

16. Палиндром — это симметричная строка, то есть она одинаково читается как слева направо, так и справа налево. Требуется разработать алгоритм, определяющий по заданной строке минимальное количество символов, которые необходимо вставить в строку для преобразования её в палиндром.
    Входные данные представляют собой строку длиной n, которая состоит из прописных (заглавных) букв от «A» до «Z», строчных букв от «a» до «z» и цифр от «0» до «9». Прописные и строчные буквы считаются различными. Результатом является одно целое число — минимальное количество вставляемых символов.
    Пример. Путем вставки двух символов строка «Ab3bd» может быть преобразована в палиндром («dAb3bAd» или «Adb3bdA»), а вставкой менее двух символов палиндром в этом примере получить нельзя.

17. Дана матрица A размером n×m с целыми числами, по модулю не превосходящими 1000. Разработать динамический алгоритм, который находит количество подматриц матрицы A, сумма элементов которых в точности равна заданному числу S.
    Например: в матрице размером 3 × 3, состоящей из единиц, количество подматриц размера 2 × 2 с суммой элементов 4 равно 4.

18. Дана матрица A размером n×m с целыми числами, по модулю не превосходящими 1000. Разработать динамический алгоритм, который находит квадратную подматрицу с максимальной суммой элементов.

19. Дано натуральное число n (n кубиков). Лесенка — это набор из ступенек, размер которых уменьшается снизу вверх. Лесенка состоит по крайней мере из двух ступенек, ступенька состоит, по крайней мере, из одного кубика.
    Например: лесенка из 3 кубиков представляет собой первую ступеньку из двух кубиков и вторую ступеньку из одного.
    Необходимо разработать алгоритм, подсчитывающий количество лесенок, которые можно составить из n кубиков.

20. Дана прямоугольная таблица (n строк, m столбцов), в клетках которой записаны целые числа. Черепашка находится в левой нижней клетке, и ей необходимо попасть в правую верхнюю клетку. Количество способов достижения конечной клетки при размере таблицы n × m равно С^n-1_n+m-2. Черепашке разрешено двигаться вверх и вправо, а также по диагонали (на одну клетку). Разработать алгоритм, подсчитывающий количество способов достижения Черепашкой конечной клетки.

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

22. Даны два натуральных числа n и k. Вычисляется kⁿ. Разрешается использовать операции умножения и возведения в степень, круглые скобки и переменную с именем k. Умножение считается одной операцией, возведению в степень q соответствует q–1 операция.
    Необходимо разработать алгоритм, определяющий минимальное количество операций, необходимых для возведения k в степень n. Желательно сделать это для как можно больших значений n.
    Например: при n = 5 необходимы три операции: (k× k)²× k.

23. На столе находится n спичек, и два игрока по очереди берут спички из кучки. Первому игроку разрешается взять от 1 до k спичек. А затем игроки могут брать любое количество спичек, но не более чем на 1 превышающее то количество, которое взял игрок перед ним (можно взять меньше или столько же, но обязательно хотя бы одну). Проигрывает тот, кто возьмет последнюю спичку.
    Например: Пусть n = 10 и k = 5. На первом ходу первый игрок может взять 1, 2, 3, 4 или 5 спичек. Если первый игрок возьмет 3 спички, то на следующем ходу второй игрок может взять 1, 2, 3 или 4 спички. А если первый игрок возьмет одну спичку, то второй затем может взять 1 или 2 спички.

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

24. Палиндром — это симметричная строка, то есть она одинаково читается как слева направо, так и справа налево. Требуется разработать алгоритм, определяющий по заданной строке минимальное количество символов, которые необходимо вставить в строку для преобразования её в палиндром.
    Входные данные представляют собой строку длиной n, которая состоит из прописных (заглавных) букв от «A» до «Z», строчных букв от «a» до «z» и цифр от «0» до «9». Прописные и строчные буквы считаются различными. Результатом является одно целое число — минимальное количество вставляемых символов.
    Пример. Путем вставки двух символов строка «Ab3bd» может быть преобразована в палиндром («dAb3bAd» или «Adb3bdA»), а вставкой менее двух символов палиндром в этом примере получить нельзя.

25. Дана матрица A размером n×m с целыми числами, по модулю не превосходящими 1000. Разработать динамический алгоритм, который находит количество подматриц матрицы A, сумма элементов которых в точности равна заданному числу S.
    Например: в матрице размером 3 × 3, состоящей из единиц, количество подматриц размера 2 × 2 с суммой элементов 4 равно 4.

26. Дана матрица A размером n×m с целыми числами, по модулю не превосходящими 1000. Разработать динамический алгоритм, который находит квадратную подматрицу с максимальной суммой элементов.

27. Дано натуральное число n (n кубиков). Лесенка — это набор из ступенек, размер которых уменьшается снизу вверх. Лесенка состоит по крайней мере из двух ступенек, ступенька состоит, по крайней мере, из одного кубика.
    Например: лесенка из 3 кубиков представляет собой первую ступеньку из двух кубиков и вторую ступеньку из одного.
    Необходимо разработать алгоритм, подсчитывающий количество лесенок, которые можно составить из n кубиков.

28. Дана прямоугольная таблица (n строк, m столбцов), в клетках которой записаны целые числа. Черепашка находится в левой нижней клетке, и ей необходимо попасть в правую верхнюю клетку. Количество способов достижения конечной клетки при размере таблицы n × m равно С^n-1_n+m-2. Черепашке разрешено двигаться вверх и вправо, а также по диагонали (на одну клетку). Разработать алгоритм, подсчитывающий количество способов достижения Черепашкой конечной клетки.

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

30. Даны два натуральных числа n и k. Вычисляется kⁿ. Разрешается использовать операции умножения и возведения в степень, круглые скобки и переменную с именем k. Умножение считается одной операцией, возведению в степень q соответствует q–1 операция.
    Необходимо разработать алгоритм, определяющий минимальное количество операций, необходимых для возведения k в степень n. Желательно сделать это для как можно больших значений n.
    Например: при n = 5 необходимы три операции: (k× k)²× k.

31. На столе находится n спичек, и два игрока по очереди берут спички из кучки. Первому игроку разрешается взять от 1 до k спичек. А затем игроки могут брать любое количество спичек, но не более чем на 1 превышающее то количество, которое взял игрок перед ним (можно взять меньше или столько же, но обязательно хотя бы одну). Проигрывает тот, кто возьмет последнюю спичку.
    Например: Пусть n = 10 и k = 5. На первом ходу первый игрок может взять 1, 2, 3, 4 или 5 спичек. Если первый игрок возьмет 3 спички, то на следующем ходу второй игрок может взять 1, 2, 3 или 4 спички. А если первый игрок возьмет одну спичку, то второй затем может взять 1 или 2 спички.

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