1 of 10

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

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

На практике динамическое программирование часто сводится к хранению в памяти решения задач меньшей размерности.

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

    • «подсчитайте количество вариантов…»
    • «как оптимально распределить…»
    • «найдите оптимальный маршрут…»

​

​

​

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

2 of 10

Задача 1. Восхождение по лестнице�

Вы поднимаетесь по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек. За один шаг вы можете подниматься на одну или на две ступеньки.

Вопрос: сколько существует различных способов подняться на 10 ступенек?

3 of 10

Задача 1. Восхождение по лестнице�

Вы поднимаетесь по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек. За один шаг вы можете подниматься на одну или на две ступеньки.

Вопрос: сколько существует различных способов подняться?

1

2

3

4

5

1

2

3

5

​

Для 3:

Первый способ: 1, 1, 1.�Второй способ: 1, 2.�Третий способ: 2, 1.

Для 2:

Первый способ: 1, 1.�Второй способ: 2.�

Для 4:

Первый способ: 1, 1, 1, 1.�Второй способ: 1, 2, 1.�Третий способ: 2, 1, 1�Четвертый способ: 1, 1, 2�Пятый способ: 2, 2.

4 of 10

Задача 1. Восхождение по лестнице�

Вы поднимаетесь по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек. За один шаг вы можете подниматься на одну или на две ступеньки.

Вопрос: сколько существует различных способов подняться?

1

2

3

4

5

1

2

3

5

8

6

7

8

9

10

13

21

34

55

89

5 of 10

Задача 1. Восхождение по лестнице�

Вы поднимаетесь по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек. За один шаг вы можете подниматься на одну или на две ступеньки.

Вопрос: сколько существует различных способов подняться?

def stairs(n):

if n == 1:

return 1

if n == 2:

return 2

a, b = 1, 2

for _ in range(2, n):

b = a + b

a = b - a

return b

6 of 10

Задача 2. 23 задание ЕГЭ�

Демо-2021. Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?

7 of 10

Задача 2. 23 задание ЕГЭ�

Демо-2021. Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?

N

1

2

3

4

5

6

7

8

9

10

KN

1

2

2

4

4

6

6

10

10

14

N

10

11

12

13

14

15

16

17

18

19

20

KN

14

14

14

14

14

14

14

14

14

14

28

8 of 10

Задача 2. 23 задание ЕГЭ�

Демо-2021. Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?

N

1

2

3

4

5

6

7

8

9

10

KN

1

2

2

4

4

6

6

10

10

14

N

10

11

12

13

14

15

16

17

18

19

20

KN

14

14

14

14

14

14

14

14

14

14

28

9 of 10

Задача 2. 23 задание ЕГЭ�

Демо-2021. Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?

N

1

2

3

4

5

6

7

8

9

10

KN

1

2

2

4

4

6

6

10

10

14

N

10

11

12

13

14

15

16

17

18

19

20

KN

14

14

14

14

14

14

14

14

14

14

28

a =[0]*11 # массив от 0 - 10

# табличка от 1 до 10

a[1] = 1

for i in range(2,10+1):

if i%2==0:

a[i] = a[i-1] + a[i//2]

else: a[i] = a[i-1]

b =[0]*21 # массив от 0 - 20

# табличка от 10 до 20

b[10] = a[-1]

# b[10] = 1

for i in range(11,20+1):

if i%2==0 and i>=20:

b[i] = b[i-1] + b[i//2]

else: b[i] = b[i-1]

print(b[20])

# print(a[10]*b[20])

# print(a[-1]*b[-1])

N

10

11

12

13

14

15

16

17

18

19

20

KN

1

1

1

1

1

1

1

1

1

1

2

10 of 10

Домашнее задание

2) Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25? 13

1) Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Прибавить 3

Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 4 результатом является число 15 и при этом траектория вычислений содержит число 8? 308