Given a gold mine of n*m dimensions, each cell in this mine contains a positive integer which is the amount of gold in tons. Initially, the miner is at the first column but can be at any row. He can move only right, diagonally right and up, or diagonally right and down. from the current cell. Find out the maximum amount of gold he can collect.

Before diving into the problem, let us first look into the concept of two problem solving techniques, called the **Greedy Approach** and the **Dynamic Programming Approach.**

**Greedy approach:**

The greedy approach is considered one…