Overview Super Mario is on the run collecting coins. In level # 1, whenever he takes a coin, the next coin is automatically blocked with an iron brick. Which coins should Mario take in order to maximize his gains? $3 $9 $2 $7 $3 $6 $9 $1 0 0 0 3$ skip Take $9 3$ skip Take $9 Take $7 Take $7 6$ skip Take $9 Take $6 Take $1 = $25 = $23 Requirements Implement the following two functions: unsigned max_coins (vector coins) This function receives a vector of coins and returns the maximum profit Mario can gain. vector coin_indices (vector coins) This function receives a vector of coins and returns the indices of the coins Mario should take to get the maximum profit. For example, function coin_indices must return [1, 3, 6] for the example provided above. Note. You should not assume that function coin_indices is called after function max_coins. These two functions must be implemented independently. To avoid duplicating code, you can define a third function that is called from within both functions. Hints This assignment, is on dynamic programming. Therefore, start by thinking of a solution that mimics one of the dynamic programming examples covered in class: Describe the optimal solution using the optimal solution of smaller sub-problems. Think of how you will store the solutions of the sub-problems in order to avoid computing them more than once. Write a bottom-up solution. A top-down solution (using memoization) might crash with a stack overflow error (the depth of the recursion is limited by how much memory there is because each recursive call reserves a record on the memory stack!)