Naruto is a Genin (beginner Ninja) in the Hidden Leaf village. He dreams of one day becoming the Hokage of the village (highest ranked Ninja). For that to happen, he has to train day and night. Most importantly, he has to practice various Ninja techniques. Ninja techniques can be divided into four elemental types: - Fire-based (Katon) techniques - Water-based (Suiton) techniques - Wind-based (Futon) techniques - Light-based (Raiton) techniques However, Naruto can only perform the first three types only (he cannot do Light-based techniques). Whenever Naruto performs a technique, his Chakra (inner energy) is consumed a little. Naruto’s Mentor (Jiraya-Sama �) is taking Naruto for a training camp. The camp will last for N days. On each training day i (where i ranges from 1 to N), Naruto is allowed to perform one Ninja technique only. Each technique consumes a different amount of chakra on different days. For example, a Fire-based technique might consume 10 chakra points on day 1 but could consume 15 chakra points on day 3 or 8 chakra points on day 4 and so on. Naruto is allowed to perform any technique he likes in any training day, however, JirayaSama doesn’t allow him to perform two techniques of the same type in two successive days. For example, If on day 1 Naruto performs a Wind-based technique, then on day 2 he is allowed to perform Water-based technique or Fire-based technique but not a Wind-based technique, because that would mean he performed two Wind-based techniques in a row which will make Jiraya-Sama angry. Find the minimum amount of Chakra needed by Naruto to finish the training camp.(SOLVE IT IN C++ OR JAVA)

Partl: Divide & Conquer 1- Define the value returned by the function fwhich we want to optimize. 2- Define the parameters which f depends on. 3- Draw the recursion tree for fusing the values from the example above. 4- Write the recursive (divide and conquer) code to solve the question.