所以问题是
给定填充有非负数的 amxn 网格，找到一条从左上角到右下角的路径，该路径最小化沿其路径的所有数字的总和。您只能向下和向右移动。
这是软件工程面试中常见的面试问题，可以通过实现动态规划表来轻松解决，以便辨别哪条路径成本最低。
我现在想知道，有没有一种简单的方法可以解决替代问题？这将是在 mxn 网格中找到路径的确切总和。
例如，输入是一个 3x3 矩阵，目标总和可以说是 4。应该使用什么类型的编程技术来找到从左上角到右下角正好等于 4 的路径。
1 回答
0
使用修剪的广度（或深度）优先搜索：
由于您只能向下和向右移动，而我们正在寻找一个确切的数字，因此您需要查看所有可能的路径。幸运的是，由于数字不是负数，我们可以对搜索进行大量修剪——只要路径前缀的成本大于您的目标（例如 4），生成的路径肯定会比您的目标具有更大的成本，所以你可以终止这个计算分支。
注意：如果你运气不好，你仍然需要查看所有 (2N - 2)!/((N-1)! * (N-1)!) 可能的路径，其中 N 是网格的边。（向下 N-1 次，向右 N-1 次，重复排列，因为向下和权利在它们自己的类别中是无法区分的。）一个这样的例子是一个网格，其中所有路径的总数都低于您的目标。
证明：假设有一条你没有检查的路径。如果我是你的敌人，并且我在了解你的算法的同时设置网格。我总是可以将未经检查的路径设置为具有目标总和的路径。
于 2020-11-26T13:52:55.020 回答