Let \(X\) be the last square where we make money during the journey. Then, we should reach \(X\) in the minimum possible number of turns (in the optimal journey, \(X\) should be the most profitable square so far, so there is no point in sacrificing turns along the way to earn small change). However, we should bring as much money as possible in that number of turns.

The same can be said for the route to \(X\). Converting this process into dynamic programming gives an \(O(N^4)\) time solution.

Sample Implementation (Python)

N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]
R = [list(map(int, input().split())) for _ in range(N)]
D = [list(map(int, input().split())) for _ in range(N - 1)]
INF = 10**18

dp = [[(INF, 0) for j in range(N)] for i in range(N)]
dp[0][0] = (0, 0)

for i in range(N):
    for j in range(N):
        dist = [[INF for x in range(j + 1)] for y in range(i + 1)]
        dist[i][j] = 0
        for y in range(i, -1, -1):
            for x in range(j, -1, -1):
                if y < i:
                    dist[y][x] = min(dist[y][x], D[y][x] + dist[y + 1][x])
                if x < j:
                    dist[y][x] = min(dist[y][x], R[y][x] + dist[y][x + 1])
                c = max(0, dist[y][x] - dp[y][x][1] + P[y][x] - 1) // P[y][x]
                t = dp[y][x][0] + c + i - y + j - x
                m = dp[y][x][1] + c * P[y][x] - dist[y][x]
                if t < dp[i][j][0] or t == dp[i][j][0] and m > dp[i][j][1]:
                    dp[i][j] = (t, m)
print(dp[N - 1][N - 1][0])