1 1 2 3 4 5 1 6 7 1

a[n] = [a_1, a_2, ..., a_n]

1) Удалите один элемент: 


1.0) Если весь массив возрастает - ничего удалять не надо 

1.1) Переберем элемент, который мы удаляем

1.2) Посмотрим, какой возрастающий подмассив образуется, если склеить массив

1.3) Удаляем a_i, важное условие - a[i - 1] < a[i + 1](иначе текущий ответ 0), 

Дальше просто жадно надо взять максимальный подмассив слева-справа 

int l[n], r[n] - сколько влево и вправо возрастает от текущего,















2) Есть массив a[n], сказать, сколько в нем арифм.прогрессий: 

То есть подмассивов длины >= 3, у которых разность соседних совпадает

Здесь можно делать это сразу же, просто поддерживаем текущую длину арифм.прогрессии

vector<pair<int, int>> dp(n) = {длина, шаг} - сколько элементов образуют прогрессию если влево от 
i-го элемента


Динамика 

Что важно:

Что храним в состояниях
Переходы
База
Где лежит ответ
Время работы + память
Как считаем - вперед или назад, порядок пересчета
O(n^3), O(n^2)

3) Есть лесенка, на каждой ступеньке число, можем прыгать вверх на 1/2, сколько максимум можно набрать 

Динамика назад:

dp[i] = max(dp[i - 1], dp[i - 2]) + a[i] - посчитали все до i - 1, пересчитываем i через пред.значения 

Динамика вперед:

Мы уже посчитали все до i, "протолкнем" i-е значение вперед 

Знаем dp[i]
dp[i + 1] = max(dp[i + 1], dp[i] + a[i + 1]);
dp[i + 2] = max(dp[i + 2], dp[i] + a[i + 2]);

4) Черепашка:


Есть поле n * m, черепашка стоит в левом верхнем углу, может двигаться вправо/вниз, хотим дойти 
в правый нижний с макс.стоимостью

Назад - dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j]
Вперед - dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a[i + 1][j])

inf - 1e9, -1e9 - стартовые значения 

dp[i] = max(dp[i - 1], dp[i - 2]) + a[i]


5) НВП - было


a[n] = [a1, a2, ..., an]


6) НОП 



Есть два массива, надо найти их наибольшую общую подпоследовательность

a = [3, 1, 4, 3], n = 4

b = [2, 2, 3, 1, 1, 5], m = 6

dp[n][m]


dp[i][j] - ответ для i, j префиксов a, b(длина НОП)

for (i = 0; i < n; i++){
	for (j = 0; j < m; j++){
		dp[i][j] = ?
	}
}

dp[i][j] = ?

1) a[i] = b[j]

dp[i][j] = dp[i - 1][j - 1] + 1

2) a[i] != b[j]

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


7)

dp[1][0] - начали в секции 1 и сфоткали все пары, у которых координата >= 1

dp[i][j] - макс.стоимость снимков, если прошло j минут и мы стоим в i-й секции 

dp[300][300]

Как считать?

for (i = 0; i < n; i++){
	for (j = 0; j < t; j++){
		c - ценность снимка, если на j-й минуте стоим в i-й секции
		dp[i][j] = 0;
		for (l = max(0, i - k); l <= min(n - 1, i + k); l++){
			dp[i][j] = max(dp[i][j], dp[l][j - 1]);
		}
		dp[i][j] += c;
	}
}