主題

LeetCode - 329. Longest Increasing Path in a Matrix 解題心得

Not In My Back Yard | 2021-05-19 00:00:05 | 巴幣 0 | 人氣 61

題目連結:


題目意譯:
給定一個 m × n 之整數矩陣,回傳矩陣中的最長遞增路徑之長度。

對於每格,你可以往四個方向移動:左、右、上或是下。你不能對角線地移動或是移出邊界(即,環繞到另一邊界是不被允許的)。

限制:
m == matrix.length
n == matrix[i].length
1 ≦ m 、 n ≦ 200
0 ≦ matrix[i][j] ≦ 2 ^ 31 - 1



範例測資:
範例 1:
輸入: matrix = [[9,9,4],[6,6,8],[2,1,1]]
輸出: 4
解釋: 最長的遞增路徑為 [1, 2, 6, 9]。

範例 2:
輸入: matrix = [[3,4,5],[3,2,6],[2,2,1]]
輸出: 4
解釋: 最長的遞增路徑為 [3, 4, 5, 6]。對角線移動是不被允許的。

範例 3:
輸入: matrix = [[1]]
輸出: 1


解題思維:
可以模仿這題的精神——避免重複地遞迴。因為路徑上的值是遞增的,所以對於某格數字所能走的路徑是固定的。

只是該題每次可以往上下左右最多 k 格,而本題只能每次往上下左右移動一格。因此本題相對來說比較「簡單」。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作