1 of 16

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

Антоненко А.С.

2022

2 of 16

Задачи максимизации – максимальная сумма

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

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10

3 of 16

Неправильное решение – жадный алгоритм

  • Идем туда, где число больше.�Идем вначале 3 раза вниз, но число 100 не получаем.

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10

4 of 16

Шаг 1: Двумерная динамика

  • Для каждой клетки i, j считаем какую можно собрать максимальную сумму до этой клетки, �начиная�из верхнего�левого угла.
  • Обозначим�M[i][j].

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10

5 of 16

Шаг 2: Начальные значения

  • Считаем значения первой строки и столбца.
  • M[0][0].
  • M[0][j].
  • M[i][0].

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10

1

1+1=2

2+2=4

4+1=5

5+2=7

11

14

19

20

6 of 16

Шаг 2: Рекуррентная формула

  • M[i][j] = max (M[i-1][j], M[i][j-1]) + A[i][j]
  • i>=1, j>=1

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10

1

2

4

5

7

11

14

19

20

11+1=12

12+1=13

13+100=113

113+2=115

14+2=16

16+2=18

113+2=115

115+2=117

19+5=24

24+5=29

115+7=122

122+7=129

24+1=25

29+1=30

122+7=129

129+10=139

7 of 16

Шаг 3: Решение

M[0][0] = A[0][0]

for (i = 1 … N - 1)

M[i][0] = M[i-1][0] + A[i][0]

for (j = 1 … K - 1)

M[0][j] = M[0][j-1] + A[0][j]

for (i = 1 … N - 1)

for (j = 1 … K - 1)

M[i][j] = max(M[i-1][j],M[i][j-1])� + A[i][j]

Ответ: M[N-1][K-1]

8 of 16

Шаг 4: Восстановление пути

  • Из конца в начало после подсчета числовых�значений

​

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10

1

2

4

5

7

11

14

19

20

12

13

113

115

16

18

115

117

24

29

122

129

25

30

129

139

9 of 16

Вариации – максимальная сумма и количество способов её получить

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

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10

10 of 16

Двумерная динамика

  • Шаг 1: для каждой клетки i, j считаем какую можно собрать максимальную сумму до этой клетки, �начиная�из верхнего�левого угла�и количество �способов.
  • Обозначим�M[i][j],�С[i][j].

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10

11 of 16

Начальные значения

  • Шаг 2: Считаем значения первой строки и столбца.
  • M[0][0].
  • M[0][j].
  • M[i][0].

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10

1

1+1=2

2+2=4

4+1=5

5+2=7

11

14

19

20

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

12 of 16

Шаг 2: Рекуррентная формула

  • M[i][j] = max (M[i-1][j], M[i][j-1]) + A[i][j]
  • i>=1, j>=1

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10

1

2

4

5

7

11

14

19

20

11+1=12

12+1=13

13+100=113

113+2=115

14+2=16

16+2=18

113+2=115

115+2=117

19+5=24

24+5=29

115+7=122

122+7=129

24+1=25

29+1=30

122+7=129

129+10=139

13 of 16

Вариации – максимальная сумма - идем из левого столбца в правый

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

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10

14 of 16

L-R динамика. �Максимальный подпалиндром

  • Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. �Напишите программу, находящую в данной строке подпалиндром максимальной длины.
  • Пример ввода: МАТЕМАТИКА

15 of 16

L-R динамика. �Максимальный подпалиндром

А

К

И

Т

А

М

Е

Т

А

М

А

К

И

Т

А

М

Е

Т

А

М

L\R

16 of 16

Вариации – максимальная сумма - идем из левого столбца в правый

  • Получить максимальную сумму, двигаясь из левого столбца в правый стобец (двигаясь� только � вниз-вправо� вправо, � вверх-вправо).
  • Необходимо�посетить �все�строки.�

1

1

2

1

2

10

1

1

100

2

3

2

2

2

2

5

5

5

7

7

1

1

1

7

10