如何知道我们应该添加的最少数字以获得完整的数组

Question

最近我遇到了这样一个问题：
假设有一个int N，还有一个int[]，这个数组中的每个元素只能使用一次。我们需要设计一个算法，通过将这些数字相加得到1到N，最后返回需要相加的最少数字
例如：

N = 6, array is [1,3]
1 : we already have.
2 : we need to add it to the array.
3 : we can get it by doing 1 + 2.
4: 1 + 3.
5 : 2 + 3.
6 : 1 + 2 + 3.
So we just need to add 2 to our array and finally we return 1.

我正在考虑使用DFS解决这个问题。你有更好的解决方案吗？谢谢！

Answer 1

这是动态规划中的一个著名问题。你可以在这里参考完整的解决方案https://www.youtube.com/watch?v=s6FhG--P7z0

Answer 2

我不知道这是否是一个好的解决方案：

我会创建第二个数组（布尔数组），记住我能计算的所有数字。然后我将编写一个方法，模拟向数组中添加一个数字。（在您的示例中，1、3和2被添加到数组中）。将更新布尔数组，以始终记住哪些值（数字）可以使用添加的数字进行计算。

在对初始数组值调用add方法后，您测试每个Number x（1

由于我的解释是不行的，我将添加（未经测试）Java代码：

static int[] arr = {3,5};
static int N = 20;
//An Array remembering which values can be calculated so far
static boolean[] canCalculate = new boolean[N];

//Calculate how many numbers must be added to the array ( Runtime O(N^2) )
public static int method(){

    //Preperation (adding every given Number in the array)
    for(int i=0; i<arr.length; i++){
        addNumber(arr[i]);
    }

    //The number of elements added to the initial array
    int result = 0;

    //Adding (and counting) the missing numbers (Runtime O(N^2) )
    for(int i=1; i<=N; i++){
        if( !canCalculate[i-1] ){
            addNumber(i);
            result++;
        }
    }
    return result;
}


//This Method is called whenever a new number is added to your array
//runtime O(N)
public static void addNumber( int number ){
    System.out.println("Add Number: "+(number));

    boolean[] newarray = new boolean[N];
    newarray[number-1] = true;

    //Test which values can be calculated after adding this number
    //And update the array
    for(int i=1; i<=N; i++){
        if( canCalculate[i-1] ){
            newarray[i-1] = true;
            if( i + number <= N ){
                newarray[i+number-1] = true;
            }
        }
    }
    canCalculate = newarray;
}

编辑：测试了代码并更改了一些错误（但Rachel的解决方案似乎无论如何都更好）

Answer 3

以下是OP发布的解决方案为何有效的解释（简单地说，该算法是遍历已排序的现有元素，保留前面现有元素的累积和，并将一个元素添加到数组中，如果它不存在并且超过当前总和，则求和）：

循环按必须形成的每个元素的顺序进行测试，并对前面的元素求和。如果需要的元素大于当前总和，它会提醒我们。如果你仔细想想，这真的很简单！当我们已经使用了前面的所有元素时，我们怎么能生成元素呢，这就是总和所表示的！

相反，当总和大于当前元素时，我们如何知道所有中间元素都能形成？例如，考虑n=7，a={}：

The function adds {1,2,4...} 
So we are up to 4 and we know 1,2,3,4 are covered,
each can be formed from equal or lower numbers in the array.

At any point, m, in the traversal, we know for sure that 
X0 + X1 ... + Xm make the largest number we can make, call it Y.
But we also know that we can make 1,2,3...Xm

Therefore, we can make Y-1, Y-2, Y-3...Y-Xm

(In this example: Xm = 4; Y = 1+2+4 = 7; Y-1 = 6; Y-2 = 5)

Q.E.D.