假设我们有一个 RXC 表。每个单元格包含一个权重。
有两个来源可供您选择，您可以从 ROW 0 开始，但可以从任何列开始。
您的目标是沿着表格向下移动，直到到达最后一行（任何列），并且不会有重叠的路径。这必须产生这两条路径的最低重量组合。
任何想法如何解决？如果您需要更多详细信息，请告诉我。
如果你能提供一些 O(constant XRXC) 运行时间，那就太好了。
编辑：每一步，你可以向左、向右或向下。
例子
1 9 1 9
1 9 1 9
1 2 3 9
6 3 9 9
最佳值是 1-1-1-6 和 1-1-3-2-3
As Said by Acess Denied , please specify the rules of travelling down the rows , For eg :- if the rule is
You can either go directly down or right-diagonally down or left diagonally down
We can do this similar to a Single source problem from the first source , and find the optimal sum , then replace the weight of cells belonging to this path to 0 , and then again run a Single source problem solution from the second source
I think this greedy approach will work as the sum of both paths is asked in final .