直到第N-1行的任何路徑的最大總和

Question

有一個N * N整數矩陣Arr[N][N]。從行r和列c，我們可以去以下三種指數：

一Arr[ r+1 ][ c-1 ] (valid only if c-1>=0)

II。 Arr[ r+1 ][ c ]

三， Arr[ r+1 ][ c+1 ] (valid only if c+1<=N-1)

所以，如果我們從第0行的任何列索引開始，到第N-1行的任何路徑的最大總和是多少。

Answer 1

就可以解決這個問題是這樣的：

令M是N×N的整數矩陣A數量最多定義一個新的N * N矩陣B，其中b[i,j] = M - a[i,j] + 1。 B只包含正整數。遍歷方法對應於矩陣細胞上的某個明確定義的方向圖。現在在這個圖上使用 dijkstra algorithm，其中上面每個節點與三個節點（或者邊上的兩個節點）節點的距離僅等於數字b[i,j]。 dijkstra算法將爲您提供該圖中的'最短'路徑，其對應於矩陣A中具有最大總和的路徑。

爲了明白爲什麼用這種方式可以解決問題，假設有x個序列s1，s2，s3，...，sx等長N.一些序列si將有最大的和。如果我們取序列t1，t2，...，tx使得t1k = -s1k，那麼最大和s是最小的和t。如果我們爲每個序列中的每個值添加一個常數，那麼具有最大和的t序列不會改變，因爲這些序列中的每一個都是相等長的。

Answer 2

這個問題可以使用動態規劃或使用遞歸來解決。 下面是使用動態規劃方法用Java編寫的溶液：
http://design-interviews.blogspot.com/2014/11/largest-sum-of-any-of-paths-till-row-n.html

溶液的時間複雜度是O（n^2）。 該解決方案更改原始輸入矩陣。如果需要保持原始矩陣不變，則需要使用另一個二維數組。