freezeYe
diff --git a/‎329.矩阵中的最长递增路径.md
Lines changed: 64 additions & 0 deletions b/‎329.矩阵中的最长递增路径.md
Lines changed: 64 additions & 0 deletions
diff --git a/‎README.md
Lines changed: 3 additions & 1 deletion b/‎README.md
Lines changed: 3 additions & 1 deletion
@@ -0,0 +1,64 @@
+### 描述:
+给定一个整数矩阵，找出最长递增路径的长度。
+对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
+
+### 示例:
+```
+示例 1:
+输入: nums = 
+[
+  [9,9,4],
+  [6,6,8],
+  [2,1,1]
+] 
+输出: 4 
+解释: 最长递增路径为 [1, 2, 6, 9]。
+
+示例 2:
+输入: nums = 
+[
+  [3,4,5],
+  [3,2,6],
+  [2,2,1]
+] 
+输出: 4 
+解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
+```
+
+### 解析:
+一道典型的动态规划问题，设record[x][y]为以x,y为终点的最长路径，依次遍历其上下左右4个节点a,b， 当matrix[a][b]满足递增条件时record[x][y]=max(record[x][y], dp(a,b)+1)，对于已经遍历过得节点直接返回当前最长路径值。
+
+时间复杂度: O(mn) / 空间复杂度: O(mn)
+
+```javascript
+/**
+ * @param {number[][]} matrix
+ * @return {number}
+ */
+var longestIncreasingPath = function(matrix) {
+    if(!matrix.length) return 0
+    let max = 0
+    const row = matrix.length
+    const column = matrix[0].length
+    const track = [{x: -1,y: 0}, {x: 1, y: 0}, {x: 0, y: -1}, {x: 0,y: 1}]
+    const record = new Array(row).fill(0).map(i=> new Array(column).fill(0))
+    const dp = (i, j)=> {
+        if(record[i][j] !== 0) return record[i][j]
+        record[i][j] = 1
+        track.forEach(point=> {
+            const dx = i + point.x
+            const dy = j + point.y
+            if(dx >= 0 && dy >= 0 && dx < row && dy < column  && matrix[dx][dy] > matrix[i][j]) {
+                record[i][j] = Math.max(record[i][j], dp(dx, dy) + 1)
+            }
+        })
+        return record[i][j]
+    }
+    for(let i=0; i<row; i++) {
+        for(let j=0; j<column; j++) {
+            max = Math.max(max, dp(i, j))
+        }
+    }
+    return max
+};
+```
@@ -2,4 +2,6 @@
 
 [1. 两数之和(简单)](./1.两数之和.md)
 
-[2. 两数相加(中等)](./2.两数相加.md)
+[2. 两数相加(中等)](./2.两数相加.md)
+
+[329. 矩阵中的最长递增路径(困难)](./329.矩阵中的最长递增路径.md)