c# - 找出 1 和 2 的所有组合，加起来等于 N

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

Find all combinations of 1 and 2 that add up to N

因此，您需要组合 而不是排列。

让我们看一些例子-

• 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:如果您还需要值，那么它会花费更多的精力，但是对于您的代码，您似乎只想找到 no。的方式。

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