Problem statement

https://binarysearch.com/problems/Maximum-Dropping-Path-Sum-With-Column-Distance-Cost/

Solution

The idea is to given row is to recalculate next row with dp in linear time. For this we need to evaluate cumulative maximums of row[j] + j when we go from left to right and cumulative maximums of row[j] - j when we go from right to left. Then we can recauculate elements for the next row.

Notice that row[j] - abs(c - j) = (row[j] - j) + c for c <= j and row[j] - abs(c - j) = (row[j] + j) - c for c >= j.

Complexity

It is O(mn) for time and O(m) for space.

Code

class Solution:
    def solve(self, M):
        n, m = len(M), len(M[0])

        row = M[0]
        for i in range(1, n):
            lft = list(accumulate([row[j] + j for j in range(m)], max))
            rgh = list((accumulate([row[j] - j for j in range(m-1,-1,-1)], max)))[::-1]
            row = [M[i][j] + max(rgh[j] + j, lft[j] - j) for j in range(m)]
        return max(row)