This exercise is about solving a problem by developing a dynamic programming algorithm. Per- form all eight steps involved in doing this. justify all your statements. You are back in the 80s game from the midterm. You enter a room, and - oh shock! - there is a monster. However, instead of swinging his axe he offers you a game. The monster tells you there are three types of treasures: jewels, swords, and shields. He hands you a jewel, and points to the sole door in the room. There is a series of rooms you will go through. The rooms are numbered in 1 to n. You will go through the rooms in order and you can never return to an earlier room. In each room is a monster that has one treasure. You can decide to exchange your current treasure for the treasure the monster has. Your goal is to earn as many points as possible. 1. If you exchang your treasure for a treasure of the same type you earn one point. 2. If you exchange your treasure for a treasure of a different type, you lose one point. Your score can be negative. 3. You can do nothing, and your score stays the same. Describe and analyze an efficient algorithm to calculate your maximum possible score. Your input is an array T[1...n], where T[i] is the type of treasure the monster in the ith room has.