1 of 29

Динамічне програмування

Сергій Жуковський

ЖДУ ім.Івана Франка

2 of 29

  • Динамічне програмування – це метод, при якому задача розбивається на підзадачі, розв’язки яких знаходяться послідовно один за одним

3 of 29

Задача Сходинки

Скількома способами можна потрапити на n ту сходинку, якщо можна ступати на наступну, переступати через одну і через дві сходинки.

4 of 29

0

1

2

3

4

5

6

1

1

​

​

​

​

​

5 of 29

0

1

2

3

4

5

6

1

1

2

​

​

​

​

6 of 29

0

1

2

3

4

5

6

1

1

2

4

​

​

​

7 of 29

0

1

2

3

4

5

6

1

1

2

4

7

​

​

S[i] = S[i-1] + S[i-2]+S[i-3]

8 of 29

0

1

2

3

4

5

6

​

1

3

2

9

7

6

Сходинки (вартість проходу)

9 of 29

Дві цифри

  • Скільки N - значних чисел можна створити з 2-х цифр 5 і 9, щоб не стояло поруч більше 2-х однакових цифр.
  • Можна створити: 559, 995, 595
  • Неможна створити 555, 999

​

10 of 29

​

1

2

3

4

5

6

7

Закінчуються 1-ю – 5

1

​

​

​

​

​

​

Закінчуються 2-ма - 5

0

​

​

​

​

​

​

Закінчуються 1-ю – 9

1

​

​

​

​

​

​

Закінчуються 2-ма - 9

0

​

​

​

​

​

​

11 of 29

​

1

2

3

4

5

6

7

Закінчуються 1-ю – 5

1

1

​

​

​

​

​

Закінчуються 2-ма - 5

0

1

​

​

​

​

​

Закінчуються 1-ю – 9

1

1

​

​

​

​

​

Закінчуються 2-ма - 9

0

1

​

​

​

​

​

Разом

2

4

​

​

​

​

​

12 of 29

​

1

2

3

4

5

6

7

Закінчуються 1-ю – 5

1

2

​

​

​

​

​

Закінчуються 2-ма - 5

1

1

​

​

​

​

​

Закінчуються 1-ю – 9

1

2

​

​

​

​

​

Закінчуються 2-ма - 9

1

1

​

​

​

​

​

Разом

4

6

​

​

​

​

​

13 of 29

​

1

2

3

4

5

6

7

Закінчуються 1-ю – 5

1

1

2

​

​

​

​

Закінчуються 2-ма - 5

0

1

1

​

​

​

​

Закінчуються 1-ю – 9

1

1

2

​

​

​

​

Закінчуються 2-ма - 9

0

1

1

​

​

​

​

Разом

2

4

6

​

​

​

​

14 of 29

​

1

2

3

4

5

6

7

Закінчуються 1-ю – 5

1

1

2

3

​

​

​

Закінчуються 2-ма - 5

0

1

1

2

​

​

​

Закінчуються 1-ю – 9

1

1

2

3

​

​

​

Закінчуються 2-ма - 9

0

1

1

2

​

​

​

Разом

2

4

6

10

​

​

​

K[i] = K[i-1]+ K[i-2]

15 of 29

Часткова сума на масиві (префікс сума)

0

1

2

3

4

5

6

7

8

9

10

11

12

12

14

​

6

2

5

4

6

7

2

3

4

5

6

2

3

5

Sum l-r - ?

16 of 29

Часткова сума на масиві (префікс сума)

0

1

2

3

4

5

6

7

8

9

10

11

12

12

14

​

6

2

5

4

6

7

2

3

4

5

6

2

3

5

0

1

2

3

4

5

6

7

8

9

10

11

12

12

14

​

6

8

13

17

23

30

32

35

38

43

49

51

54

59

ps[i] = ps[i-1] + mas[i]

17 of 29

Часткова сума на масиві (префікс сума)

0

1

2

3

4

5

6

7

8

9

10

11

12

12

14

​

6

2

5

4

6

7

2

3

4

5

6

2

3

5

0

1

2

3

4

5

6

7

8

9

10

11

12

12

14

​

6

8

13

17

23

30

32

35

38

43

49

51

54

59

ps[i] = ps[i-1] + mas[i]

Sum l-r = ps[r] – ps[l-1]

18 of 29

Часткова сума на матриці

​

1

2

3

4

5

6

1

1

2

3

4

6

4

2

3

2

3

6

7

1

3

2

4

3

1

1

1

4

1

1

4

1

1

1

5

1

2

3

4

4

4

Sum r1,s1,r2,s2 - ?

19 of 29

Часткова сума на матриці

​

1

2

3

4

5

6

1

1

2

3

4

6

4

2

3

2

3

6

7

1

3

2

4

3

1

1

1

4

1

1

4

1

1

1

5

1

2

3

4

4

4

​

0

1

2

3

4

5

6

0

​

0

0

0

0

0

0

1

0

1

3

6

10

​

​

2

0

4

8

14

24

​

​

3

0

6

14

23

?

​

​

4

0

​

​

​

​

​

​

5

0

​

​

​

​

​

​

ts [i][j] = ts[i-1][j] +ts[i][j-i] - ts[i-1][j-1] + mas[i][j]

20 of 29

Sum r1,s1,r2,s2 = ts [r2][s2] – ts[r2][s1-1] - ts[r1-1][s2] + ts[r1-1][s1-1]

21 of 29

Найбільша спільна підпослідовність

Задано дві послідовності. Знайдіть довжину їх найбільшої спільної підпослідовності (підпослідовність - це те, що можна отримати із заданої послідовності викреслюванням деяких елементів).

5

4 1 2 7 3

7

2 1 8 7 6 3 9

Переборний алгоритм О(2N)

22 of 29

​

0

1 (4)

2 (1)

3 (2)

4 (7)

5 (3)

0

0

0

0

0

0

0

1 (2)

0

0

0

1

1

1

2 (1)

0

0

1

1

1

1

3 (8)

0

0

1

1

1

1

4 (7)

0

0

1

1

2

2

5 (6)

0

0

1

1

2

2

6 (3)

0

0

1

1

2

3

7 (9)

0

0

1

1

2

3

5

4 1 2 7 3

7

2 1 8 7 6 3 9

23 of 29

for(int i=1; i<=n1; i++)

for(int j=1; j<=n2; j++)

{

if(a[ i ]==b[ j ]){

c[ I ][ j ]=c[ i - 1 ][ j – 1 ]+1;

}

else

{

c[ i ][ j ]=max( c[ i - 1 ][ j ], c[ i ][ j – 1 ] );

}

}

24 of 29

Задача Цв’яхи

  • На прямій дощечці вбито цвяхи. Довільні два цвяхи можна з'єднати ниточкою. Потрібно з'єднати деякі пари цвяшків ниточками так, щоб до кожного цвяха була прив'язана хоча б одна ниточка, а сумарна довжина усіх ниточок була мінімальною.

25 of 29

Викладення плитки 2*n

26 of 29

Викладення плитки 3*n

Скількома способами можна замостити 3 x n прямокутник за допомогою 2 x 1 кісток доміно? Нижче наведено приклад замощення такими плитками прямокутника 3 x 12.

27 of 29

Викладення плитки

  • Un кількість різних викладань 3*n.
  • Vn – кількість викладань 3*n прямокутника без лівого нижнього кута (3n – 1)/2 плиток.

​

  • U0 = 1, U1 = 0, Un = 2Vn-1 + Un-2
  • V0 = 0, V1 = 1, Vn = Un-1 + Vn-2

​

​

28 of 29

Викладення плитки

В масивах u и v будемо обчислювати значеня Un и Vn.

int u[31], v[31];

Обчислимо значення Un и Vn (n = 0, 1, …, 30) відповідно до наведених вище рекурентним формулам.

u[0] = v[1] = 1;

u[1] = v[0] = 0;

for(n = 2; n <= 30; n++)

{

u[n] = 2 * v[n-1] + u[n-2];

v[n] = u[n-1] + v[n-2];

}

​

29 of 29

Дякую за увагу

​

Сергій Жуковський

ЖДУ ім.Івана Франка