Exercise $1-3$

$(15$ Marks$)$

Given an integer target which represents the total distance to be covered by a robot on a straight road, and an array powerups $[]$ of size N representing a number of power ups where $i^{th}$ power up is powerups $[$i$][0]$ positions away from the start and gives powerup$[$i$][1]$ amount of health units. The robot can take an infinite amount of power ups and starts with M health units. The task is to find the minimum number of times the robot has to collect power ups to reach target when it uses one unit of health for moving one unit distance. Note: If the robot reaches the $i^{th}$ power ups with $0$ health units left, it can collect the power up to increase his health.

Examples:a$)$ Write the recursive formulation of the optimal substructure of a Dynamic Programming algorithm to solve the above problem.b$)$ Can the above problem be solved optimally using a greedy algorithm? If yes, describe such algorithm using precise English statements. If not, explain why.

Answer the previous question with pen on paper showing your workout