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 of the most straightforward approach which can be applied to a variety of problems. Most of these problems have *n* inputs and require us to obtain a subset that satisfies some constraints/conditions. A subset which satisfies the constraints is called a **feasible** solution. Our main goal is to find a feasible solution that either maximizes or minimizes an objective function. A feasible solution that does this is an **optimal** solution. Usually, the feasible solutions are derived quite easily but that is not always the case for the optimal solutions. …