Problem Link - Training
Problem Statement
Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route for the journey so that it passes through N cities, numbered 1, 2, …, N, and in this order.
When they set out, Pikachu has an initial strength of Sin as well as an experience value (XV) of 0. As they travel they may increase his strength and experience value in a manner to be described below.
In each city, Ash can choose either to train Pikachu or let Pikachu battle the Gym-leader (but not both). The Gym-leader in ith city has experience E[i]. If Pikachu enters a city i with strength S and decides to train, then this increases his strength by the cube of the sum of the digits in his current strength. For example, if he entered a city with a strength of 12, then training will increase his strength to 12 + (1+2)3 = 39. On the other hand, if he enters city i with strength S and battles the Gym-leader, then this increases his experience value XV by S*E[i].
Ash wants your help to find out the maximum XV that Pikachu can attain at the end of his journey.
Approach
The solution involves using dynamic programming to track the maximum experience Pikachu can achieve after each city for a given number of training sessions. An array dp is used, where dp[j] represents the maximum experience Pikachu can have after visiting a city with exactly j training sessions. The training increases strength by adding the cube of the sum of the digits of the current strength, and this is calculated before making decisions at each city. For each city, two choices are considered: either train, which increases the training count, or battle the Gym-leader, which increases experience based on the current strength and Gym-leader’s experience value. By iterating over each possible number of training sessions, the solution keeps track of the best possible experience value. The final result is the maximum value in the dp array after all cities have been processed.
Time Complexity
The time complexity is O(N^2) due to iterating over each city and each possible training session.
Space Complexity
The space complexity is O(N) for storing the experience values in the dynamic programming array.