找到加起来为N的1和2的所有组合

Question

说我有这样的功能.我需要知道将加起来为N的1和2的所有组合.有没有更好的方法来编写这个对于大整数(如N = 1200或12000)表现更好的方法？

public static int Combos(int n)
{
    if (n < 3)
    {
        return n;
    }
    else
    {
        return Combos(n - 1) + Combos(n - 2);
    }
}

Answer 1

找到加起来为N的1和2的所有组合

所以,你需要combinations而不是排列.

让我们看一些例子 -

• 1 = {1}
• 2 = {1,1},{2}
• 3 = {1,1,1},{1,2}(或{2,1},两者相同).
• 4 = {1,1,1,1},{1,2,1},{2,2}
• 5 = {1,1,1,1,1},{1,2,1,1},{2,2,1}
• 6 = {1,1,1,1,1,1},{1,2,1,1,1},{2,2,1,1},{2,2,2}
• 7 = {1,1,1,1,1,1,1},{1,2,1,1,1,1},{2,2,1,1,1},{2,2,2 ,1}

如果您观察,它看起来像这样 -

• 1 = 1
• 2 = 2
• 3 = 2
• 4 = 3
• 5 = 3
• 6 = 4
• 7 = 4
• 8 = 5

您可以在以下O(1)时间和O(1)空间内解决此问题 -

public static int Combos(int n){
    return n / 2 + 1;
}   

注意#1:如果您还需要值,那么需要花费更多精力,但是使用您的代码看起来您​​只想找不到.方式

注意#2:如果您注意到,找到实际值也不会花费太多精力.您根本不需要记住以前的结果.