Collect all coins in minimum number of steps in Greedy method in Python

In this tutorial, we will learn how to collect all coins in a minimum number of steps in Python. The process of collecting coins should be contiguous. So, here we have used the greedy method to solve this kind of problem. We will discuss each step to understand the greedy method and try to solve this question.

What is the Greedy method

  • used in optimization problems and to find an optimal solution.
  • more efficient
  • finds the optimal solution in every step
  • follows the top-down approach
  • example: Fractional Knapsack

How to use this method in this problem

Using this greedy method, we simply solve this problem. First, we take a stack of coins and then we select the coins along both horizontal and vertical direction. Then we have to use the recursion function to get the actual result. So, each step we will try to obtain the optimal solution.

Here, we have used two functions i.e. minimum_steps and coin_collection. The coin_collection function has two arguments i.e. the given stack and the length of the stack. The minimum_steps function contains the main algorithm and it follows the recursion manner to return the right output.

Below is our Python code to collect all coins in minimum number of steps in Greedy method:

def minimum_steps(string, low, high, steps): 
    if low >= high: 
        return 0
    temp = low 
    for i in range(low, high): 
        if string[i] < string[temp]: 
            temp = i 
    return min(high - low, 
            minimum_steps(string, low, temp, string[temp]) +
            minimum_steps(string, temp + 1, high, string[temp]) +
            string[temp] - steps) 


def coin_collection(string, n): 
    return minimum_steps(string, 0, n, 0) 

string = [ 2, 1, 1, 2, 2, 3, 4 ] 
n = len(string) 
print(coin_collection(string, n))

Output:

5

Also read: Print maximum number of A’s using given four keys in Python

Leave a Reply

Your email address will not be published. Required fields are marked *