1) Задача о рюкзаке



Есть n предметов, каждый весит w[i] и стоит c[i], и есть рюкзак веса W

100 предметов, 10000 - максимальный вес



Надо набрать предметов на наибольшую стоимость, каждый предмет можно 1 раз

Пусть вес = 10 

w[0] = 7, c[0] = 14

w[1] = 5, c[1] = 9

w[2] = 5, c[2] = 9


Будем делать динамику

dp[i][j], i - элемент, который сейчас рассматриваем, (i - 1 мы уже рассмотрели), 

j - вес рюкзака, dp[i][j] = макс.стоимость, на которую можно набрать предметов в рюкзак веса j, 
если использовать только первые i предметов

dp[n - 1][W]

O(n * W)

W = 4

w[0] = 3, c[0] = 1
w[1] = 2, c[1] = 2
w[2] = 2, c[2] = 1


       0 1 2 3 4
i = 0: 0 0 0 1 0 
i = 1: 0 0 2 1 0 
i = 2: 0 0 2 1 3


Как посчитать dp[i][j]?

Изначально, пусть dp[i][j], i != 0 dp[i][j] = dp[i - 1][j]

dp[i][j] = max(dp[i][j], c[i] + dp[i - 1][j - w[i]])


dp[i][j - w[i]] либо он равен dp[i - 1][j - w[i]], 
либо он больше, но тогда мы для этого состояния динамики мы использовали i-й предмет - а больше 1 
раза нельзя использовать

2) Можно сделать вариацию с бесконечным количеством всех предметов 

Изначально, пусть dp[i][j], i != 0 dp[i][j] = dp[i - 1][j]

Далее попробуем использовать w[i] предмет 

dp[i][j] = max(dp[i][j], c[i] + dp[i][j - w[i]])

dp[i - 1][j - w[i]] <= dp[i][j - w[i]] - поэтому нам не важен предыдущий уровень


3)

Нам дано n 

Можем использовать от 1 до n 

Сколько пилообразных последовательностей длины n из этих чисел можно написать?

Вывести ответ по модулю 1e9 + 7

ans - огромный ответ, ans % mod

Пилообразная - каждый элемент либо больше своих соседей, либо меньше 

n = 100

n = 5

1 2 1 2 1

dp[i], i - сколько символов уже поставили(ставим i-й)

dp[i][j], j - последний символ

dp[i][j] - количество способов сделать пилообразную последовательность длины i, 
где последнее число j

Перебираем dp[i - 1][l]

l < j


n = 3

		1 2 3 
i = 0:  1 1 1
i = 1:  2 2 2
i = 2:    4 

1 3 2, 2 3 2,  2 1 2, 3 1 2

  
Нам еще нужна дополнительная информация про то, предпоследний элемент больше ли / меньше последнего 

dp[i][j][0] - длина i, последний j и он больше предпоследнего 
dp[i][j][1] - длина i, последний j и он меньше предпоследнего


dp[i][j][0] - хотим посчитать

for (l = 0; l < j; l++){
	dp[i][j][0] += dp[i - 1][l][1];
}

dp[i][j][1]:


for (l = j + 1; j <= n; l++){
	dp[i][j][1] += dp[i - 1][l][0];
}


n^2 состояний, пересчет за n - O(n^3)

Можно оптимизировать
Мы могли бы посчитать префиксные суммы

p[i][j][0] - сумма dp[i][l][0], l <= j 
p[i][j][1] - сумма dp[i][l][1], l <= j

Мы посчитали i-й слой

Давай просто посчитаем p[i]

Получаем O(n^2)


4)

Для любых строчек/векторов определене лексикографический порядок 

Строчка s1 < s2, 

либо если s1 - префикс s2 

либо если у них есть какой-то общий префикс и следующая за ним буква в s1 меньше, чем в s2 

a 
ac
aaa

Для каждой строчки есть множество индексов, куда можно прийти с минимальным ответом 






bbba

string dp[n][n]

dp[i][j] - минимальная строка, которую можно получить, придя в эту ячейку 

Всего квадрат состояний, в каждом хранится строка длины n 

dp[i][j] - пересчитываем из верхней + верхней слева, сравнение двух строчек 
длины n работает за n 

O(n^3)

dp[i][j] - смотрим на dp[i - 1][j]


dp[i][j] = 0/1 - можем ли прийти в эту ячейку с минимальным ответом 


Из всех единичек смотрим куда можем перейти 

И записываем единичку в клетки с минимальным символов 

 
Есть строчка s 

dp[l][r] - ответ для подстроки с l по r