我有一个数组，我必须计算数种将其分成3个连续部分的方式，以使它们的总和相等。如何修改分区问题呢？例如-令A为包含{{1,2,3,0,3}的数组答案-2因为它可以分为{{1,2}，{3}，{0,3}}和{{1,2}，{3,0}，{3}}相等的和。
如果我对您的理解正确，说明您在限制问题，从而无法重新排列数组中值的顺序。假设问题集合理，您可以轻松遍历并测试每个可能的变化。这将是递归的，但无需动态编程。我前面没有IDE，但是我相信代码看起来像这样（适应所选语言）：
public int countWays(Array array) {
int count = 0;
int sum = 0;
for (int index = 0; index < array.length(); ++index) {
// how much would each partition sum to if we partitioned here?
sum += array.get(index);
// how many ways could the rest of the array be split to match that sum?
count += recursiveCount(sum, array.subArray(index + 1, array.length());
}
return count;
}
public int recursiveCount(int partitionSum, Array remaining) {
// base case
if (remaining.length() == 0) {
return 1;
}
int count = 0;
int sum = 0;
for (int index = 0; index < remaining.length(); ++index) {
// how much would this partion sum to if we partitioned here?
sum += remaining.get(index);
// did we hit the mark?
if (sum == partitionSum) {
// make a partion here and see if we can finish the rest of the array
count += recursiveCount(paritionSum, remaining.subArray(index + 1, remaining.length());
}
}
return count;
}
*注：这假定一个subArray函数创建一个从第一个索引（包括第一个索引）到第二个索引（专门）的NEW数组。我相信这是大多数库中最常见的行为。
您对输入的了解越多，可以添加更多捷径来使其更高效。例如;如果您知道该数组仅包含正数，那么当您的总和大于目标值时，您可以停止测试分区，因为无论您添加什么正数，它都永远不会将总和降低到目标值。
在提出的问题中，我们需要在一个总和相同的数组中找到三个连续的部分。我将提及这些步骤以及可为您解决问题的代码段。
这里我们要做的是，从头开始遍历数组直到len（array）-3。在找到总和sum / 3时，就说索引i，我们得到了所需的前半部分。
现在，不必关心后半部分，并将等于end [i + 2]的值添加到解变量（初始为零）中。 end [i + 2]告诉我们从i + 2到结尾的总次数，以获得第三部分的总和等于sum / 3。
这里，我们所做的是第一部分和第三部分的内容，我们也已经完成了第二部分的内容，默认情况下，第二部分等于sum / 3。我们的解决方案变量将是问题的最终答案。
下面是为了更好地理解上述算法的代码段：:-
这里我们正在进行向后扫描，以存储从每个索引的末尾获得sum / 3的方法的数量。
long long int *end = (long long int *)calloc(numbers, sizeof(long long int);
long long int temp = array[numbers-1];
if(temp==sum/3){
end[numbers-1] = 1;
}
for(i=numbers-2;i>=0;i--){
end[i] = end[i+1];
temp += array[i];
if(temp==sum/3){
end[i]++;
}
}
一旦有了end数组，我们就进行正向循环并获得最终解决方案
long long int solution = 0;
temp = 0;
for(i=0;i<numbers-2;i++){
temp+= array[i];
if(temp==sum/3){
solution+=end[i+2];
}
}
solution存储最终答案，即将数组拆分为三个具有相等总和的连续部分的方式的数目。
这里是一个正确的工作解决方案，其中有两个基于@Mattew Pape答案的示例。但这是尝试所有可能分区的蛮力方法。可以进一步优化。此方法的复杂度为O（N！）。
public class partitonArray {
static int total = 0;
public static int countWays(int [] arr) {
int sum = 0;
for (int index = 0; index < arr.length; ++index) {
sum += arr[index];
List<List<Integer>> lst = new ArrayList();
List<Integer> l1 = new ArrayList();
for(int j=0;j<=index;j++)
l1.add(arr[j]);
lst.add(l1);
recursiveCount(sum, Arrays.copyOfRange(arr, index + 1, arr.length), lst);
}
return total;
}
public static void recursiveCount(int partitionSum, int [] remaining, List<List<Integer>> lst) {
// base case
if (remaining.length == 0 && lst.size() > 1) {
System.out.println("Result here = "+lst.toString());
total++;
}
int sum = 0;
List<Integer> l1 = new ArrayList();
for (int index = 0; index < remaining.length; ++index) {
sum += remaining[index];
l1.add(remaining[index]);
// did we hit the mark?
if (sum == partitionSum) {
// make a partion here and see if we can finish the rest of the array
lst.add(l1);
recursiveCount(partitionSum, Arrays.copyOfRange(remaining, index + 1, remaining.length), lst);
lst.remove(l1);
}
}
}
public static void main(String [] args) {
//int [] arr ={ 2, 4, 6,7, 7, 6, 3, 3, 3, 4, 3, 4,5, 4, 4, 3, 3, 1,4};
int [] arr = {1, 2, 3, 0, 3};
System.out.println(countWays(arr));
}
}
**Output**:
Result here = [[1, 2], [3], [0, 3]]
Result here = [[1, 2], [3, 0], [3]]
2
/*
Result here `enter code here`= [[2, 4, 6, 7], [7, 6, 3, 3], [3, 4, 3, 4, 5], [4, 4, 3, 3, 1, 4]]
Result here = [[2, 4, 6, 7, 7, 6, 3, 3], [3, 4, 3, 4, 5, 4, 4, 3, 3, 1, 4]]
2
*/