c++ - 有限空间内存

Question

在尝试提高我对 this contest 的回答速度时，我有一个函数，它接受两个值 n 和 k 并产生一个输出。重复计算，所以我正在记住它。我不能使用二维数组，因为 n 和 k 的约束是 10^5!所以我正在使用 map :

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;
}

但显然，这种方法太慢了。我的内存有问题吗？或者我可以像数组一样获取恒定时间提取，而不是从 map 中获取对数提取吗？

这个函数解决了这个循环:

f(x,0) = x 和 f(x,1) = (x-1)/2

可以用更好的方法解决这个问题吗？非常感谢。

Answer 1

小改进:记住 find 返回的迭代器并取消引用它而不是使用 operator[]。