Problem statement

<font color = bluehttps://binarysearch.com/problems/Collecting-Disappearing-Coins

Solution

This is 2d-version of problem Equal to leetcode Leetcode 0198. House Robber. Indeed, we can not take from the adjacent rows and then for each taken row we can not take from adjacent elements. So, apply robber for each row and then apply robber for resulting array.

Complexity

It is O(mn) for time and O(n) for space, where n is the number of rows.

Code

class Solution:
    def solve(self, M):
        def robber(nums):
            dp1, dp2 = 0, 0
            for num in nums:
                dp1, dp2 = dp2, max(dp1 + num, dp2)          
            return dp2

        return robber([robber(x) for x in M])