Leetcode 3459. Length of Longest V-Shaped Diagonal Segment

• Leetcode 3459. Length of Longest V-Shaped Diagonal Segment
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3459. Length of Longest V-Shaped Diagonal Segment

1. 解题思路

这一题我的思路上就是一个动态规划加上剪枝的思路。

首先，不难给出一个动态规划算法来考察每一个位置作为起始点时其所能获得的最大V字路径长度，但是，贸然地动态规划会出现超时的问题。

因此，我们需要对其进行一下合理的剪枝，具体来说，就是考察一下每一个位置所能获得的最大路径长度，如果当前计算得到的路径长度已经大于等于其所能获得的最大路径长度了，那我们就不需要考察当前作为作为起点时的情况了。

2. 代码实现

给出python代码实现如下：

class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        next_direction = {
            (1, 1): (-1, 1),
            (1, -1): (1, 1),
            (-1, 1): (-1, -1),
            (-1, -1): (1, -1)
        }

        @lru_cache(None)
        def dp(i, j, turn, dx, dy):
            if turn == 0:
                ans = 1
                while 0 <= i+dy < n and 0 <= j+dx < m and grid[i+dy][j+dx] == 2-grid[i][j]:
                    ans += 1
                    i, j = i+dy, j+dx
                return ans
            if grid[i][j] == 1:
                ans = 1
                for dx, dy in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
                    if 0 <= i+dy < n and 0 <= j+dx < m and grid[i+dy][j+dx] == 2:
                        ans = max(ans, 1 + dp(i+dy, j+dx, 1, dx, dy))
                return ans
            
            ans = 1
            if 0 <= i+dy < n and 0 <= j+dx < m and grid[i+dy][j+dx] == 2-grid[i][j]:
                ans = max(ans, 1 + dp(i+dy, j+dx, 1, dx, dy))
            dx, dy = next_direction[(dx, dy)]
            if 0 <= i+dy < n and 0 <= j+dx < m and grid[i+dy][j+dx] == 2-grid[i][j]:
                ans = max(ans, 1 + dp(i+dy, j+dx, 0, dx, dy))
            return ans
        
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    if ans >= max(min(n-i+1, m-j+m), min(i+1, j+m), min(i+n, m-j+1), min(n-i+n, j+1)):
                        continue
                    ans = max(ans, dp(i, j, 1, 1, 1))
                    if ans == max(min(n, 2*m-1), min(m, 2*n-1)):
                        break
        return ans

提交代码评测得到：耗时8412ms，占用内存156MB。