Мемоизация в ограниченном пространстве
Пытаясь увеличить скорость моего ответа для этот конкурс, У меня есть функция, которая принимает два значения n а также k и производит вывод. Расчеты повторяются, поэтому я запоминаю это. Я не могу использовать 2D-массив, так как ограничения для n а также k являются 10^5! Итак, я использую карту:
std::map<std::pair<int,int>,double> m;
double solve(int n, int k)
{
if(k==0) return n;
if(k==1) return (n-1)/2.0;
std::pair<int,int> p = std::make_pair(n,k);
std::map<std::pair<int,int>,double>::iterator it;
if( (it=m.find(p)) != m.end())
return it->second;
double ans = 0;
for(int i=1 ; i<=n-1 ; i++)
ans += solve(i,k-1);
ans = ans/n;
m[p] = ans;
return ans;
}
Но, видимо, этот подход слишком медленный. Есть ли какая-то проблема с моим напоминанием? Или я могу получить выборки с постоянным временем как массив вместо логарифмических выборок с карты?
Эта функция решает это повторение:
f(x,0) = x а также f(x,1) = (x-1)/2
Может ли это быть решено лучше? Заранее большое спасибо.
Решение
Незначительное улучшение: запомните итератор, возвращенный методом find, и разыменуйте его вместо использования operator [].
Другие решения
Вам не нужно хранить двумерный массив значений. Вместо того, чтобы запоминать, переверните проблему и используйте динамическое программирование.
Чтобы сэкономить время, обратите внимание, что f(x, y) = 0 если x <= y,
Рассчитать значения f(i, 0) за 1 <= i <= x - k и хранить их в одномерном массиве. Затем рассчитайте f(i, 1) за 2 <= i <= x - k + 1, f(i, 2) за 3 <= i <= x - k + 2и так далее, пока не получите f(i, k - 1) за k <= i <= x - 1, Тогда вы можете рассчитать f(x, k), На каждом шаге вам нужно только два массива длины x - k,
расчета f(i, j) принимает i - j - 1 дополнения и деление. поэтому общее время составляет is ((х — к)2 к). Но это быстрее, если сначала вычислить суммы, а затем разделить, потому что каждая сумма всего на один элемент больше, чем предыдущая, поэтому общее время составляет ϴ ((x — k) k).