329. Longest Increasing Path in a Matrix 矩阵中的最长递增路径

转载 作者：大佬之路 更新时间：2024-01-31 14:20:21 24 4

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

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0])
        res = 0
        cache = [[-1] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                path = self.dfs(matrix, cache, m, n, i, j)
                res = max(res, path)
        return res
        
    def dfs(self, matrix, cache, m, n, i, j):
        if cache[i][j] != -1:
            return cache[i][j]
        directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        res = 1
        for dire in directions:
            x, y = i + dire[0], j + dire[1]
            if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] <= matrix[i][j]:
                continue
            path = 1 + self.dfs(matrix, cache, m, n, x, y)
            res = max(path, res)
        cache[i][j] = res
        return cache[i][j]

24 4 0

• java - 熟悉 Java 中的线程 : Why does this program's runtime increase with increasing number of threads

  情况 我正在尝试熟悉 Java 中的线程。出于这个原因，我修改了我在一本书中找到的程序列表。所做的事情非常简单: 它创建一个包含 100.000.000 个元素的 boolean[] 数组。 它使用

• html - 基础顶部导航栏 : Increase Width

  我正在使用 Zurb Foundation 使用以下代码制作导航栏:

• c - 如果整数序列的后续数字大于前一个，则显示 'increasing'

  Write a program that reads a sequence of integers and print 'increasing' if each subsequent number i

• c++ - 如何 "do, if expression increased"？

  我有比特币源代码(多线程)，我打算添加一些新行。在比特币网络上，数据消息在数据存储在 vector 中的地方交换。我想在 vector 大小增加时执行一些指令: 如何在 C++ 中编写以下模式以便在

• algorithm - 网络流中的 'increasing Edge'

  We are given a network flow, as well as a max flow in the network. An edge would be called increasin

• Java2D : Increase the line width

  我想增加 Line2D 的宽度。我找不到任何方法来做到这一点。我是否需要为此实际制作一个小矩形？ 最佳答案 您应该使用 setStroke 来设置 Graphics2D 对象的笔画。 http://w

• 334. Increasing Triplet Subsequence 递增的三元子序列

  题目地址：https://leetcode.com/problems/increasing-triplet-subsequence/description/ 题目描述： Given an unso

• 300. Longest Increasing Subsequence 最长递增子序列

  题目地址：https://leetcode.com/problems/longest-increasing-subsequence/description/ 题目描述 Given an unsor

• 738. Monotone Increasing Digits 单调递增的数字

  题目地址：https://leetcode.com/problems/monotone-increasing-digits/description/ 题目描述： Given a non-negat

• python - 从零开始的逻辑回归 : error keeps increasing

  我已经从头开始实现逻辑回归，但是当我运行脚本时，算法总是预测错误的标签。我尝试通过将所有 1 切换为 0 来更改训练输出和 test_output，反之亦然，但它总是预测错误的标签。 我还注意到，将“

• python - KivyMD 按钮 : How increase its dimensions

  我正在尝试增加kivyMD 按钮 的宽度 和高度，但它不受支持(size_hint)。 •我应该创建自己的继承自 Button 类的按钮类吗？ •考虑到我希望我的应用程序在 Android 上运行，这

• java - 这是 "Increase"ArrayList 大小的最佳方法吗？

  ArrayList tempArray = new ArrayList<>(size); 我正在为我的合并排序构建一个 tempArray，它将根据上下文对整数或字符串进行排序。因此类型为 T Arr

• indexing - 如何: Increase Lucene .净索引速度

  我正在尝试创建大约200万条记录的Lucene。索引时间约为9小时。 您能否建议如何提高性能？ 最佳答案 我写了一篇关于如何并行化Lucene索引的可怕文章。它确实写得很糟糕，但是您会发现它是here

• mongodb : Increasing max connections in mongodb

  我需要你的帮助来解决这个问题 这是我的 ulimit -a 的结果在我的 linux 服务器上 core file size (blocks, -c) 0 scheduling

• linux-kernel - 虚拟 : How it increase performance

  我想了解: 与完全虚拟化或硬件辅助虚拟化(如 virtio_net 或 virtio_blk)相比，virtio 驱动程序如何提高性能？ 这些 virtio 驱动程序如何影响 VMEXIT/VMENT

• MATLAB 玫瑰图 : increasing radial increments?

  我正在使用 rose2.m 生成许多角度直方图。我希望显示每个箱子中元素数量的比例范围在 0-50 之间，对于所有地 block 以 10 为增量增加，即使特定地 block 上的最大元素数量小于 5

• ios - 音频单元录音 : increased volume of buffers

  我正在为我使用远程音频单元的 iPhone 构建一个录音应用程序。在对传入缓冲区执行一些音频分析后，我使用以下方法将缓冲区写入磁盘: ExtAudioFileWriteAsync 但是，我遇到的问题是

• java - 问题: ArrayList size increasing

  您好，我正在解析 xml 文件，我正在返回 Objects 类的 ArrayList，但是对于此方法的每次调用，ArrayList 的大小为从 0-8 和 8 增加到 16 和 24...而不是创建一

• Django 测试 : increase testsRun counter

  在一些 Django 测试中，我有循环来测试很多东西。 在最终结果中它显示为: Ran 1 test in 3.456s 我想为每个循环增加该计数器，我该怎么做？ 它正在使用 subTest() ，但

• c - 指针算术 : By how much is y increased?

  我正在努力解决这个指针算术: int x; int *y = &x; ++y; y 增加了多少？ 我知道:“&”是引用运算符，可以读作“address of”。“*”是解引用运算符，可以读作“指向的值