递归分割数组

Question

递归分割数组

3

我需要获取将数组分成小子数组的所有可能方式的数量。我们可以在垂直和水平方向上分割数组。我的算法效果很好，但时间复杂度太高。你能看一下如何改进它吗？参数 nStart - 子数组的第一行 nEnd - 子数组的最后一行 mStart, mEnd - 用于第二维（列）。 check() - 检查结束条件的函数 return - 分割数组的不同方式的数量。我们在函数检查返回true时进行分割。

public static long divide(int nStart, int nEnd, int mStart, int mEnd) {
    long result = 0;

    for(int i = 1; i < nEnd - nStart; i++) {
        if(check(nStart, nStart + i, mStart, mEnd) && check(nStart + i, nEnd, mStart, mEnd))
            result += divide(nStart, nStart + i, mStart, mEnd) * divide(nStart + i, nEnd, mStart, mEnd);
    }

    for(int i = 1; i < mEnd - mStart; i++) {
        if(check(nStart, nEnd, mStart, mStart + i) && check(nStart, nEnd, mStart + i, mEnd)) 
            result += divide(nStart, nEnd, mStart, mStart + i) * divide(nStart, nEnd, mStart + i, mEnd);
    }

    return (result == 0 ? 1 : result) % 1000000000; 
}

例子

输入

2 2 10 01

输出 2

输入

3 2 101 010

输出 5

我认为您需要了解如何使用check（）函数。当下一个子数组仅具有1或仅具有0时，我们停止除法。这是代码：

public static boolean check(int nStart, int nEnd, int mStart, int mEnd) {
    if((nEnd - nStart) + (mEnd - mStart) == 2) 
        return false;
    for(int i = mStart; i < mEnd; i++) {
        for(int j = nStart; j < nEnd; j++) {
            if(bar[i][j] != bar[mStart][nStart])
                return true;
        }
    }
    return false;
}

- John

在我看来，这个问题似乎可以不使用递归解决。您能否提供一些样例输入和期望的输出？可以是一个2x2的数组。 - akhil_mittal

1

请不要破坏您的帖子。 - M.A.R.

4

请不要破坏您的帖子。它已经得到了赞，所以人们认为它有价值。 - user456814

请问您能否在描述中添加示例中隐含的其他限制条件？在我看来，一个2x2矩阵可以垂直和水平地分成4 choose 2 + 4 choose 3 + 4 choose 4 = 11种不同的方式。 - גלעד ברקן

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fluster · Accepted Answer

通过查看您的代码，我可以看到在递归的每个步骤中，您将二维数组分成两个数组，其中一个是水平切割，另一个是垂直切割。然后，您验证这些部分是否都满足您定义的check方法的某些条件，如果是，则将这两个部分放入递归中。当递归无法继续时，返回1。下面我假设您的算法始终产生所需的结果。

恐怕这个算法的有效优化高度依赖于check条件的内容。在简单情况下，它总是返回true，当问题变成一个直接的数学问题时，可能有一个通用的非递归解决方案。稍微复杂一些，但仍然可以有效地解决的是，条件只检查数组的形状，这意味着例如check（1,5,1,4）将返回与check（3,7,5,8）相同的结果。

最复杂的当然是通用解决方案，其中检查条件可以是任何内容。在这种情况下，对于你的暴力解决方案，没有太多可以优化的，但我想到一件事情，那就是为你的算法添加一个内存。你可以使用java.awt.Rectangle类（或创建自己的类）来保存子数组的维度，然后有一个java.util.HashMap来存储divide方法执行的结果以备将来参考，如果再次使用相同的参数调用该方法。这将防止可能发生的重复工作。

因此，您可以在类中定义haspmap作为静态变量：

static HashMap<Rectangle,Long> map = new HashMap<Rectangle,Long>();

然后在分割方法的开始添加以下代码：

Rectangle r = new Rectangle(nStart,mStart,nEnd,mEnd);
Long storedRes = map.get(r);
if (storedRes != null) {
    return storedRes;
}

然后你将该方法的结尾改为form：

result = (result == 0 ? 1 : result) % 1000000000;
map.put(r, result);
return result;

这应该能提高算法的性能。

回到我之前的想法，如果检查条件足够简单，那么这种优化甚至可以更有效地完成。例如，如果您的检查条件仅检查数组的形状，则只需要将其宽度和高度作为映射的键，这将减小映射的大小并增加其中的正数命中次数。