Problem statement

https://binarysearch.com/problems/Maximum-Product-Path-in-Matrix/

Solution

Equal to Leetcode 1594. Maximum Non Negative Product in a Matrix.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, G):
        m, n = len(G), len(G[0])
        
        @lru_cache(None)
        def dp(i, j):
            if i == 0 and j == 0: return (G[0][0], G[0][0])
            cands = []
            if i > 0:
                min1, max1 = dp(i - 1, j)
                cands += [min1 * G[i][j], max1 * G[i][j]]
            if j > 0:
                min2, max2 = dp(i, j - 1)
                cands += [min2 * G[i][j], max2 * G[i][j]]
            return min(cands), max(cands)
        
        mn, mx = dp(m-1, n-1)
        return -1 if mx < 0 else mx % (10**9 + 7)