使用动态规划找到最大数量

Question

给定一个硬币n(<=10^9)，我可以用它兑换3个硬币：n/2、n/3和n/4（其中/代表楼层划分）。我最多能赚到多少？我的代码是：

#include <iostream>
using namespace std;
int a[10000000];
long int coin(long int n){
    if(n<10000000){
        return a[n];
    }
    else{
        return(max(n,coin(n/2)+coin(n/3)+coin(n/4)));
    }
}
int main()
{
    //cout << "Hello World!" << endl;
    long int n,ans;
    int i;
    a[0]=0;
    for(i=1;i<10000000;i++){
        a[i]=max(i,a[i/2]+a[i/3]+a[i/4]);
    }
    while(cin>>n){
        if(n<10000000){
            cout<<a[n]<<endl;
        }
        else{
            ans=coin(n);
            cout<<ans<<endl;
        }
    }
    return 0;
}

我怎样才能改善它的时间和 space 复杂性？问题：https://www.hackerearth.com/problem/algorithm/bytelandian-gold-coins/description/

Answer 1

一些想法，还没有确定的答案。

首先，我觉得你的做法很合理。您的数字最多为 10^9，您无法对所有数字进行预处理。相反，您考虑到较小的数字 "somehow" 被该过程更频繁地选择，因此您只记忆到某个上限，这里是 10^7.
您的基本算法的一个简单改进是意识到您只需要记住 2 或 3 的倍数。所有其他输入都可以很容易地与 count 函数中的那些数字相关联。
另一个优化可能是根据经验改变上限 10^7。也就是，在10^5和10^8之间选择一些值，然后交出执行时间最短的那个。

改进这种基本方法并非易事，但改进它的方法是深入了解号码选择过程。基本上，应该记住那些被选中的次数多的数字，而那些被选中的次数不多的数字。

这里可以做很多事情，但通常必须在您提交给比赛的程序中即时生成记忆程序所基于的所需结果。我想这使得很难提出有竞争力的解决方案。我可以想象 "memoize all below 10.000"、"memoize multiples of 5 above 10.000"、"memoize multiples of 7 above 10.000" 等形式的简单规则可能会有用。这样的规则可以很容易地编码到程序中而不需要太多内存。例如，它们可以通过遗传算法提前找到。

对于一种精确的方法，可以假设问题中的硬币数量均匀分布。然后可以遍历所有数字 i 直到 10^9 并获取每个数字 k<i 被程序选择的频率。结果是一个数组count[i]。接下来，您为 count[i] 选择一个下限 L 并记住 i 其中 count[i]>=L 的所有数字。但是，如前所述，此过程成本太高，因为它必须在运行本身中完成。

你可以做的是只选择，比方说，N 最常选择的数字，并在代码中对它们进行硬编码。实际包含的记忆数 N 可以根据任务中的内存限制来确定。

使用动态规划找到最大数量

Find greatest amount using dynamic programming

c++

algorithm

time-complexity

dynamic-programming

space-complexity