假设我有这个非常常见的 DP 问题（动态编程） -
给定成本矩阵 cost[][] 和 cost[][] 中的位置 (m, n)，编写一个函数，返回从 (0, 0) 到达 (m, n) 的最小成本路径的成本。矩阵的每个单元格代表遍历该单元格的成本。到达路径的总成本 (m, n) 是该路径上所有成本的总和（包括源和目的地）。您只能从给定单元格向下、向右和对角向下遍历单元格，即从给定单元格 (i, j)、单元格 (i+1, j)、(i, j+1) 和 (i+1, j+1) 可以遍历。您可以假设所有成本都是正整数。
PS：回答这个 - 8
现在，在解决了这个问题之后..以下问题在我脑海中闪过。
假设我有 1000*1000 矩阵。并且 O(n^2) 将需要一些时间（在英特尔 i5 上肯定小于 1 秒）。但我可以进一步减少它吗？说使用此算法启动 6-8 个线程，然后将它们同步回来最终得到答案？得到答案会很快甚至在逻辑上可能吗？或者我应该把这个想法扔掉
我将从算法改进开始。无需测试 N 2 个解决方案。
一个关键是您输入正方形的方向。如果您通过向下移动进入它，则无需检查右侧的方块。同样，如果您通过向右移动进入它，则无需检查从那里向下的路径。直角转弯的目的地总是可以通过对角线移动到达，省去一个正方形及其正的重量/成本。
就线程而言，我可以看到（至少）几种拆分方式。一种方法是在您进入广场时简单地将请求排队。即，它不是（例如）测试另一个方块，而是将请求排队以测试它的两个或三个出口。N 个线程处理这些请求，这些请求会产生更多请求，一直持续到所有请求都到达终点。
这有一个明显的缺点，即在串行代码可能会放弃它们之后，您可能会继续遍历某些路线，因为它们已经比您迄今为止绕行的最短路线更长。
另一种可能性是启动两个线程，一个向前遍历，另一个向后遍历。在每一个中，您都可以找到沿对角线到任何给定点的最短路径，然后您将通过这些候选者进行纯线性扫描以找到最短的总和。
一般来说，在这样的小问题上（如您所说的 < 1 秒），由于协议开销（线程启动和同步），并行计算的效率低于顺序计算。另一个问题可能是，您增加了缓存未命中率，因为您正在从输入中选择要“随机”（非线性）操作的数据。然而，当涉及到更大的问题时，比如条目数是 10 倍的矩阵，它肯定值得考虑（或两个）。
这是一个可能的解决方案。给定一个 16x16 矩阵，我们将其切成 4 个相等的正方形。对于这些方块中的每一个，一个线程负责。每个小方块中的数字表示，经过多少个时间单位，可以计算出该方块中的结果。
因此，总时间为 33 个单位（无论单位是多少）。与 64 个单元的顺序解决方案相比，它只是它的一半。你可以说服自己任何 2^kx 2^k 矩阵的运行时间都是 2^(2k - 1) + 1。
然而，这只是我想到的第一个想法。我希望外面的世界有（更快）的并行解决方案。
更重要的是，出于我在回答开头提到的原因，出于所有实际目的，我的解决方案无法实现 2 的加速。