В предыдущей задаче на больших $N$ полный перебор невозможен. Данную задачу можно решить более быстрым алгоритмом, реализующим метод динамического программирования. Суть метода заключается в том, что в начале решается задача минимальной размерности, далее, на основании этого решения - задача следующей размерности, и т. д., пока не будет решена задача требуемой размерности. При решении задачи размерности $k$ на основании уже решенной $k-1$ размерности, решение принимается на основании так называемого принципа оптимальности Белмана - поиск максимума или минимума.

## 1. Решение предыдущей задачи методом динамического программирования (как это делалось на ЕГЭ)
Исходный массив **A**:

|5|7|1|8|2|
|---|---|---|---|---|
|3|9|2|5|6|
|7|6|1|2|7|
|5|4|3|2|8|
|9|9|6|1|2|
  
Итоговый массив **B**:

|5|12|13|21|23|
|---|---|---|---|---|
|8|21|23|28|34|
|15|27|28|30|41|
|20|31|34|36|49|
|29|40|46|47|51|
  
Заполняя на основании исходного массива $A$ итоговый массив $B$, мы в ячейке $B[n-1][n-1]$. Для всех элементов массива $B$ кроме тех, которые стоят в 1 строке и 1 столбце, значение вычисляется по формуле $B[i][j] = Max(A[i][j]-B[i-1][j]; A[i][j]+B[i][j-1])$. Это называется принцип оптимальности.  
Если требуется найти не только максимальное значение суммы, но и путь, по которому эта сумма была получена, это можно сделать, двигаясь от элемента массива $B[n-1][n-1]$ к элементу $B[0][0]$, по "жадному" алгоритму:

|1|1|1|1|1|
|---|---|---|---|---|
|1|2|3|4|5|
|1|3|6|10|15|
|1|4|10|20|35|
|1|5|15|35|70|
  
Получается треугольник Паскаля.  
$\sum{^n_{k=0}}{(n/k)a^k*b^{n-k}}$ - формула количества путей
## 2. Задача о министерстве
Некто хочет подписать бумагу у министра. Министр подписывает документ, если на нем стоит подпись любого работника с последнего этажа министерства. Каждый работник сидит в отдельном кабинете. Количество кабинетов на этаже $1\leq M\leq 500$, количество этажей $1\leq N\leq 100$. Каждый работник подписывает документ, если на нем стоит подпись из кабинета ниже под ним или из одного из соседних кабинетов. За свою подпись каждый работник берет некоторую взятку. Известны суммы взяток в каждом кабинете министерства. Требуется найти путь от 1 этажа министерства к последнему, чтобы конечная сумма взяток была минимальной.  
Для решения заведем 3 двумерных массива: в первом (**A**) хранятся исходные данные - суммы взяток в каждом кабинете, во втором (**B**) будем просчитывать наилучшие взятки для каждого кабинета, в третьем (**C**) будем отмечать путь (откуда мы пришли в данный кабинет): 0 - снизу, -1 - слева, 1 - справа.  
Массив **A**:

|10|10|1|10|
|---|---|---|---|
|10|10|1|10|
|1|1|1|10|
|1|10|10|10|
  
Массив **B**:

| 22  | 23  | 6   | 25  |
| --- | --- | --- | --- |
| 12  | 13  | 5   | 15  |
| 2   | 3   | 4   | 14  |
| 1   | 10  | 10  | 10  |
  
Массив **C**:

|0|0|0|0|
|---|---|---|---|
|0|0|0|-1|
|0|-1|-1|-1|
|0|0|0|0|
  
После заполнения массивов **B** и **C** в последней заполненной строке находим минимум. Это и будет итоговое значение взятки. Путь по министерству найдем, пользуясь массивом **C**.
## 3. Задача о рюкзаке
Имеется $N$ видов предметов, масса одного предмета $i$-го вида - $m_i$, стоимость одного предмета $i$-го вида - $S_i$​. Количество предметов каждого вида не ограничено.  
Имеется рюкзак, который может выдержать массу $m_р$. Сколько предметов каждого вида нужно поместить в рюкзак, чтобы суммарная стоимость предметов в рюкзаке была максимальной, но рюкзак не порвался?  
Для решения будем просчитывать все рюкзаки начиная с $m_n=0$ и заканчивая последним значением. Сначала в каждый из рюкзаков будем пытаться поместить 0, 1, 2, ... предметов второго вида, заполняя остаток предметами первого, а этот остаток уже прочитан.  
**Пример:**  
$m_р = 5$  
**1 type** - $m_1=2$, $S_1=5$  
**2 type** - $m_2=1$, $S_2=2$  
**3 type** - $m_3=3$, $S_3=10$  

| $m_р$ | 1 type        | 2 type                  | 3 type |
| ----- | ------------- | ----------------------- | ------ |
| 0     | $n=0$, $s=0$  | $n_1=0$, $n_2=0$, $s=0$ |        |
| 1     | $n=0$, $s=0$  | $n_1=0$, $n_2=1$, $s=2$ |        |
| 2     | $n=1$, $s=5$  | $n_1=1$, $n_2=0$, $s=5$ |        |
| 3     | $n=1$, $s=5$  | $n_1=1$, $n_2=1$, $s=7$ |        |
| 4     | $n=2$, $s=10$ |                         |        |
| 5     | $n=2$, $s=10$ |                         |        |