Ленивая динамика.: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «==Ленивая динамика== Если сложно придумать порядок обхода таким образом, чтобы все преды...») |
Глеб (обсуждение | вклад) |
||
Строка 25: | Строка 25: | ||
Также можно заметить, что в такой динамике мы посещаем только действительно нужные состояния, что в некоторых задач приводит к более приятной асимптотике. | Также можно заметить, что в такой динамике мы посещаем только действительно нужные состояния, что в некоторых задач приводит к более приятной асимптотике. | ||
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 13:51, 22 октября 2019
Ленивая динамика
Если сложно придумать порядок обхода таким образом, чтобы все предыдущие значения уже были посчитаны, то можно вместо циклов использовать рекурсивную функцию и запоминать посчитанный результат, чтобы не считать несколько раз одно и то же.
Решим, например, обычную задачу о рюкзаке таким образом. Изначально все $dp[i][j]=-1$, это будет обозначать, что значение еще не посчитано, кроме $dp[0][j]=0$.
1 int calc(int i, int j) {
2 if (dp[i][j] == -1) {
3 dp[i][j] = calc(i - 1, j);
4 if (a[i] <= j) {
5 dp[i][j] = max(dp[i][j], calc(i - 1, j - a[i]) + c[I]);
6 }
7 }
8 return dp[i][j];
9 }
10
11 answer = 0
12 for (int j = 0; j <= W; j++) {
13 answer = max(answer, calc(n, j))};
14 }
Время работы так же составит $O(nW)$, так как каждое значение мы считаем только один раз, но истинное время работы будет в несколько раз больше, потому что константа на вызовы функции значительно выше чем на простой цикл.
Также можно заметить, что в такой динамике мы посещаем только действительно нужные состояния, что в некоторых задач приводит к более приятной асимптотике.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin