leetcode-741-Cherry-Pickup

发表于 更新于 分类于 阅读次数：

描述

一张边长为n的二维矩阵, 0表示可走, -1表示障碍物(不可走), 1表示樱桃(可走, 走过之后变为0因为被摘掉了). 从0,0往返n-1,n-1的路上, 最多摘多少樱桃.

思路

其实可以看做两个人同时从0,0出发, 同时到达n-1, n-1, 最多摘到多少樱桃. 如果两个人位置相同并且当前是樱桃, 那么只摘一次. 开一个三维dp数组, dp[r1][c1][c2]表示甲从r1, c1出发, 乙从r2, c2出发, 最多摘的数量. 因为到达当前状态的步数是相同的, 所以r1+c1 == r2+c2, r2的值可以用前三个变量表示出来.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def cherryPickup(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        N = len(grid)
        memo = [[[-1] * N for _ in xrange(N)] for __ in xrange(N)]
        
        def dp(r1, c1, c2):
            r2 = r1 + c1 - c2
            if (N == r1 or N == r2 or N == c1 or N == c2 or
                    grid[r1][c1] == -1 or grid[r2][c2] == -1):
                return float('-inf')
            if r1 == c1 == N-1:
                return grid[r1][c1]
            if memo[r1][c1][c2] == -1:
                res = grid[r1][c1] + (c1 != c2) * grid[r2][c2]
                res += max(dp(r1, c1+1, c2+1), dp(r1+1, c1, c2+1),
                           dp(r1, c1+1, c2), dp(r1+1, c1, c2))

                memo[r1][c1][c2] = res
            return memo[r1][c1][c2]

        return max(0, dp(0, 0, 0))