所有这些问题都归结为计算编辑距离。简单地计算给定矩阵和零矩阵之间的Levenshtein距离的变体，其中编辑被轰炸替换，使用动态编程来存储中间数组之间的距离。我建议使用矩阵的哈希作为键。在pseudo-Python:

memo = {}

def bomb(matrix,i,j):
    # bomb matrix at i,j

def bombsRequired(matrix,i,j):
    # bombs required to zero matrix[i,j]

def distance(m1, i, len1, m2, j, len2):
    key = hash(m1)
    if memo[key] != None: 
        return memo[key]

    if len1 == 0: return len2
    if len2 == 0: return len1

    cost = 0
    if m1 != m2: cost = m1[i,j]
    m = bomb(m1,i,j)
    dist = distance(str1,i+1,len1-1,str2,j+1,len2-1)+cost)
    memo[key] = dist
    return dist

蛮力!

我知道它效率不高，但即使你找到了一个更快的算法，你也可以对这个结果进行测试，以了解它有多准确。

使用一些递归，像这样:

void fn(tableState ts, currentlevel cl)
{
  // first check if ts is all zeros yet, if not:
  //
  // do a for loop to go through all cells of ts, 
  // for each cell do a bomb, and then
  // call: 
  // fn(ts, cl + 1);

}

你可以通过缓存来提高效率，如果不同的方法导致相同的结果，你不应该重复相同的步骤。

阐述:

如果轰炸单元格1,3,5的结果与轰炸单元格5,3,1的结果相同，那么，对于这两种情况，您不应该重新执行所有后续步骤，只需1就足够了，您应该将所有表状态存储在某个地方并使用其结果。

表统计信息的散列可以用于快速比较。

这个贪婪的解决方案似乎是正确的:

正如评论中指出的那样，它在2D中会失败。但也许你可以改进它。

1 d: 如果至少有2个数字，你不需要从最左边的那个开始射击，因为从第二个开始射击并不差。所以射到第二个，而第一个不是0，因为你必须这么做。移动到下一个单元格。不要忘记最后一个单元格。

c++代码:

void bombs(vector<int>& v, int i, int n){
    ans += n;
    v[i] -= n;
    if(i > 0)
        v[i - 1] -= n;
    if(i + 1< v.size())
        v[i + 1] -= n;
}

void solve(vector<int> v){
    int n = v.size();
    for(int i = 0; i < n;++i){
        if(i != n - 1){
            bombs(v, i + 1, v[i]);
        }
        else
            bombs(v, i, v[i])
    }
}

对于2D: 再次强调:你不需要在第一行拍摄(如果有第二行)。所以要射到第二个。解决第一行的1D任务。(因为你需要使它为空)。下降。别忘了最后一排。

你可以使用状态空间规划。 例如，使用A*(或其变体之一)加上启发式f = g + h，如下所示:

G:到目前为止投下的炸弹数量 H:网格中所有值的总和除以9(这是最好的结果，意味着我们有一个可接受的启发式)

这可以用深度为O(3^(n))的树来求解。其中n是所有平方和。

首先考虑用O(9^n)树来解决问题是很简单的，只需考虑所有可能的爆炸位置。有关示例，请参阅Alfe的实现。

接下来我们意识到，我们可以从下往上轰炸，仍然得到一个最小的轰炸模式。

Start from the bottom left corner. Bomb it to oblivion with the only plays that make sense (up and to the right). Move one square to the right. While the target has a value greater than zero, consider each of the 2 plays that make sense (straight up or up and to the right), reduce the value of the target by one, and make a new branch for each possibility. Move another to the right. While the target has a value greater than zero, consider each of the 3 plays that make sense (up left, up, and up right), reduce the value of the target by one, and make a new branch for each possibility. Repeat steps 5 and 6 until the row is eliminated. Move up a row and repeat steps 1 to 7 until the puzzle is solved.

这个算法是正确的，因为

有必要在某一时刻完成每一行。 完成一行总是需要一个游戏，一个在上面，一个在下面，或者在这一行内。 选择在未清除的最低行之上的玩法总是比选择在该行之上或该行之下的玩法更好。

在实践中，这个算法通常会比它的理论最大值做得更好，因为它会定期轰炸邻居并减少搜索的大小。如果我们假设每次轰炸都会减少4个额外目标的价值，那么我们的算法将运行在O(3^(n/4))或大约O(1.3^n)。

Because this algorithm is still exponential, it would be wise to limit the depth of the search. We might limit the number of branches allowed to some number, X, and once we are this deep we force the algorithm to choose the best path it has identified so far (the one that has the minimum total board sum in one of its terminal leaves). Then our algorithm is guaranteed to run in O(3^X) time, but it is not guaranteed to get the correct answer. However, we can always increase X and test empirically if the trade off between increased computation and better answers is worthwhile.

Pólya说:“如果你不能解决一个问题，那么有一个更容易解决的问题:找到它。”

显然更简单的问题是一维问题(当网格是单行时)。让我们从最简单的算法开始——贪婪地轰炸最大的目标。什么时候会出问题?

给定11 11，贪婪算法对先炸毁哪个单元格无关。当然，中心单元格更好——它一次将所有三个单元格归零。这就提出了一种新的算法a，“炸弹最小化剩余的总和”。这个算法什么时候会出错?

给定1 1 2 11 1，算法A在轰炸第2，第3或第4单元格之间是无所谓的。但是轰炸第二个单元格，留下0 0 11 11比轰炸第三个单元格，留下10 10 10 10 1好。如何解决这个问题?轰炸第三个单元格的问题是，左边的功和右边的功必须分开做。

“炸弹使剩余的总和最小化，但使左边(我们轰炸的地方)的最小值和右边的最小值最大化”如何?叫这个算法b，这个算法什么时候出错?

编辑:在阅读了评论之后，我同意一个更有趣的问题将是改变一维问题，使其两端连接起来。很乐意看到这方面的进展。