\(d[i][j]\) を「マス \((1,1)\) からマス \((i,j)\) に移動したときの通過するマスの宝石の価値の総和の最大値」とします。

\(d[1][1]=A_{i,j}\) です。また、\(d[i][j]=\max(d[i-1][j],d[i][j-1])+A_{i,j}\) です。

この遷移に基づいて計算した時の \(d[N][M]\) の値が求める答えとなります。

実装例(Python3)

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
d = [[0] * m for _ in range(n)]
d[0][0] = 0
for i in range(n):
    for j in range(m):
        val = 0
        if i != 0:
            val = max(val, d[i - 1][j])
        if j != 0:
            val = max(val, d[i][j - 1])
        d[i][j] = val + a[i][j]
print(d[-1][-1])