algorithm - 迷宫遍历数字和

Question

给出了一个 NxN 的网格。每个点都分配了一个值，比如 num

从1,1开始我们要遍历到N,N。

如果 i,j 是当前位置，我们可以向右或向下移动。 如何通过沿任何路径从 1,1 遍历到 n,n 来找到最小数字和 任意两点可以有相同的数字 例如

1 2 3

4 5 6

7 8 9

1+2+3+6+9 = 21 n <=10000000000

输出 21 有人可以解释如何解决这个问题吗？

Answer 1

这是一个动态规划问题。这里的子问题是到达任何给定广场的最低成本/路径。因为你只能向下和向右移动，所以只有两个方格可以让你进入一个给定的方格，一个在上面，一个在左边。因此，到达正方形 (i,i) 的成本是 min(cost[i-1][i], cost[i][i-1]) + num。如果这会使您超出范围，请仅考虑网格内的选项。从左到右计算每一行，首先计算顶行，然后依次向下计算。您在 (N,N) 处获得的成本将是最小成本。