Участник:Бушенкова Ксения/LeetCode Cherry Pickup

Материал из DISCOPAL
< Участник:Бушенкова Ксения
Версия от 16:16, 25 мая 2020; StasFomin (обсуждение | вклад) (Массовая правка: удаление Категория:На проверку)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Бушенкова Ксения 16:11, 24 мая 2020 (MSK) https://leetcode.com/problems/cherry-pickup/

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        N = len(grid)
        dp = [[[float('-inf')]*N for _ in range(N)] for _ in range(2*N-1)]
 
 
        dp[0][0][0] = grid[0][0]
 
        for t in range(1,2*N-1):
 
            for i1 in range(max(0, t-N+1), min(t,N-1)+1):
                for i2 in range(max(0, t-N+1), min(t,N-1)+1):
                    if grid[i1][t-i1] == -1 or grid[i2][t-i2] == -1:
                        continue
 
                    dp[t][i1][i2] = max(dp[t-1][pre_i1][pre_i2] for pre_i1 in (i1-1,i1) for pre_i2 in (i2-1,i2) if pre_i1>=0 and pre_i2>=0)
 
                    dp[t][i1][i2]+=(grid[i1][t-i1] + (i1!=i2)*grid[i2][t-i2])
 
        return max(0, dp[2*N-2][N-1][N-1])