How to solve this dynamic programming problem?

Question

Algorithms

A rectangular island is divided into squares so that its dimensions are N x M squares. A certain number of gold coins are buried in each square, these data are stored in a matrix (two-dimensional array) Z, where Z[i, j] is the number of coins in the square with coordinates (i, j). The pirate wants to move from the southwest corner of the island to the northeast, and he can only move north or east. How can a pirate collect the most coins? Write a program that finds the pirate's optimal path and the number of coins he can collect.

Answer 1

This is a standard DP exercise.
F(i,j) - the maximum number of coins that can be collected by arriving at the point (i, j).
F(0,0) = Z[0,0]
F(i,j) = Z[i,j] + max(F(i-1,j), F(i,j-1))
F(- 1,*) = F(*,-1) = -100500
answer - F(n,m)
To restore the path, store in each cell which side the maximum is taken from - top or left. And expand the answer from the end to these links.