使用置换和递归的性能有限

Question

我正在编写一个程序，该程序计算通过其概率加权的最长条纹，并使用递归来获取所有可能的情况。这是我正在做的编码挑战：https : //open.kattis.com/problems/winningstreak

我注意到，由于递归，对于较大的输入，我拥有的置换函数并不是最有效的。输入示例为3，它将为matchs数组添加以下内容：000、010、001、011、100,110,101,111

public static void Permutations(string text, int numberOfGames,     List<String> matches)
    {
        if (numberOfGames > 0)
            for (int j = 0; j < 2; j++)
                Permutations(text + j.ToString(), numberOfGames - 1, matches);
        else
        {
            matches.Add(text.ToString());
        }

    }

我的问题在于较大的输入（示例500），因为这会导致程序崩溃并引发错误：垃圾收集器无法为主要堆段分配16384字节的内存。还有其他方法可以改善此递归，以便在较大的输入上更好地运行吗？

感谢大伙们！

Answer 1

我的问题在于较大的输入（例如500）

您的程序尝试生成包含2 ⁵⁰⁰的列表^字符串。

大约有²²⁶⁷宇宙原子。

我发现您的内存不足已不足为奇。

寻找更聪明的解决方案来解决您的问题。

请记住，问题不在于“列举所有可能的游戏组合”。问题是推导出最长条纹的长度的期望值。当组合的数量变大时，生成所有可能的组合并汇总每种组合中最长条的长度将不起作用。

还请记住，问题的陈述是结果必须在准确结果的一小部分之内。它不一定是确切的结果。在处理这样的难题时，请使用元推理：提出难题的人可能不会轻轻松松地解决问题，除非您可以利用它。

这是否使您对如何解决问题有所了解？

如果您需要更多提示和见解，请先阅读以下内容：

http://gato-docs.its.txstate.edu/mathworks/DistributionOfLongestRun.pdf