时间戳

首页 > 解决方案 > 矩阵中的最长增加路径通过 calc maxmium path sum 应用贪心

algorithm - 矩阵中的最长增加路径通过 calc maxmium path sum 应用贪心

问题描述

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

通常贪婪不会适用于最长增长路径。

所以我想创建一个相同长度的新二维矩阵，其中将存储最大路径总和，对于上面的矩阵，如下所示：

   [9 ,18,22],
   [15,24,32],
   [17,25,33]

现在我想在这个矩阵上应用贪心，即。上、左、右、下之间哪个更大，我将在坐标处移动，并将步长增加 1，直到从 0,0 到达 2,2。

但是在创建最大路径和矩阵之后，我有点困惑，因为我该如何在 dfs 中进行处理，如上所述。我是 dp 和图形问题的新手。

标签： algorithmdynamic-programming

解决方案

推荐阅读