Dynamic Programming Hacker Rank Solutions

Candies
Alice is a kindergarten teacher. She wants to give some candies to the children in her class. All the children sit in a line (their positions are fixed), and each of them has a rating score according to his or her performance in the class. Alice wants to give at least 1 candy to each child. If two children sit next to each other, then the one with the higher rating must get more candies. Alice wants to save money, so she needs to minimize the total number of candies given to the children.
Stock Maximize
Your algorithms have become so good at predicting the market that you now know what the share price of Wooden Orange Toothpicks Inc. (WOT) will be for the next N days.
Each day, you can either buy one share of WOT, sell any number of shares of WOT that you own, or not make any transaction at all. What is the maximum profit you can obtain with an optimum trading strategy?
Red John is Back
There is a wall of size 4xN in the victim’s house. The victim also has an infinite supply of bricks of size 4x1 and 1x4in her house. Gale Bertram wants to know the total number of ways in which the bricks can be arranged on the wall.
Bricks Game Optimal Strategy
You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2 or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. You have to play so that you obtain the maximum possible score. It is given that your friend will also play optimally and you make the first move.
Knapsack without weight
Given a list of integers, , and another integer, representing the expected sum. Select zero or more numbers from such that the sum of these numbers is as near as possible, but not exceeding, to the expected sum.
- Each element of can be selected multiple times.
- If no element is selected then the sum is 0.
This problem is quite similar to coin change proglem except that we don’t need to figure out the number of ways to change the sum. We just need to know if S can be changed by using values from the array. If not then we need to find the maximum sum that can be changed. First we create a table to track if sum i can be changed. Then we add values from the array one by one.
Mandragora Forest
The evil forest is guarded by vicious mandragoras. Each ith mandragora has H[i] health points . Garnet and her pet begin their journey through the evil forest with strength S=1 points and experience P=0 points. For each undefeated mandragora , she can perform either of the following actions:
- Garnet’s pet eats mandragora . This increments S by 1 and defeats mandragora .
- Garnet’s pet battles mandragora . This increases P by S x H[i] experience points and defeats mandragora
Each mandragora can only be defeated once, and Garnet can defeat the mandragoras in any order. Given the respective health points for each mandragora, can you find the maximum number of experience points she can earn from defeating all mandragoras?
We first calculate the experience by defeat all monster, then sort the monster health array. Start from the moster with the smallest health, and calculate the experience if pe eats this monster.
