Problem Statement

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…

Sakshi Singhvi

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store