优化递归函数

Question

我正在创建一个程序，它仅使用 1、2、6 和 13 返回获得数字 (n) 所需的最少总和。它非常适合 n 的小值，但一旦 n 达到像 200 这样的值程序花费太多时间来计算结果。

因此，我有两个问题：

1.有没有办法让递归更快？

2.我应该避免使用递归并使用循环吗？

这是注释的代码：

#include <iostream>
#define MAX 500000

using namespace std;

void cal(int inp, int &mini, int counter = 0);

int main (void)
{
    //Gets input
    int n;
    cin >> n;

    //Defines mini as the MAX result we can get
    int mini = MAX;

    //Calls the function
    cal(n, mini);

    //Prints the best result
    cout << mini << endl;

    return 0;
}

void cal(int inp, int &mini, int counter)
{
    //Breaks recursion if it finds an answer
    if(!inp)
    {
        if(counter<mini) mini = counter;
        return;
    }

    //Breaks recursion if the input is negative
    //or the counter is more than the best result
    else if((inp<0) || (counter>mini)) return;

    //Counts amount of recursions
    counter++;

    //Tries every combination
    cal(inp-13, mini, counter);
    cal(inp-6, mini, counter);
    cal(inp-2, mini, counter);
    cal(inp-1, mini, counter);

    return;
}

谢谢

Answer 1

问题是你的蛮力。让我建议一些更好的东西：

预备：如果有两个 1，最好使用 2。如果有 3 个 2，最好使用 6。如果有 13 个 6，最好使用 6 个 13。

因此，任何可接受的总和总是看起来像n = 13m+k1、2k和 6 的总和。通过预备知识，我们知道最佳总和k永远不会超过1+2*2+12*6 = 77。（反之亦然。当然，任何低于 78 的数字都最好在没有 13 的情况下编写。）因此，暴力破解这些值就足够了。然后您可以使用查找表。

这仍然可以进一步优化，但不应在 200 时崩溃。

假设您已找到前 77 个条目（也可以优化），您可以执行以下操作（仍未优化;-）：

int num_13 = ((n-78) / 13) + 1;
int sum_length = MAX;
for (i = num_13; i*13 < n; i++) {
    int tmp = entries_77[n-i*13]+i;
    if (tmp < sum_length) {
        num_13 = i;
        sum_length = tmp;
    }
}

我会更快地编译模 13 的等价类数组，因为对于任何给定的等价类，任何超过 78 的数字都将具有相同的k.