Image for post
Image for post

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 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. …

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