Last Updated: 14 Aug, 2022
Weird Game
Moderate
Ninja and his friends are playing a weird game. The game consists of ‘N’ levels, and each level can be played in ‘M’ different difficulty modes.
For the first level you can start the game with any difficulty mode and for the subsequent levels, you can either play it with one mode lower or one mode above or equal to the previous difficulty mode, i.e. If you played the ith level in jth mode, then you can play i+1th level in either j+1th (j < M) or j-1th (j > 1) or jth mode.
On completion of each level player is awarded some points based on the difficulty mode he played the level.
Points awarded in the ith level played in jth difficulty mode will be ‘POINTS[i][j]’.
Score of the game is defined as the sum of points obtained after completion of each level.
Determine the maximum score a player can get if he optimally plays the game.
You can start the game with any difficulty mode.
Note: In the Problem Statement 1-based indexing is used and in the code 0-based indexing is used.
Example:
Input: ‘N’ = 3 ‘M’ = 3 ‘POINTS’ = [ [ 1, 4, 3 ], [ 2, 9, 11 ], [ 6, 1, 1 ] ]
Output: 19
The optimal strategy would be:-
Playing the first level in 2nd difficulty mode with 4 points.
Playing the second level in 2nd difficulty mode with 9 points.
Playing the third level in 1st difficulty mode with 6 points.
So we get a total score of 19 points.
Input Format :
First line contains ‘T’, denoting the number of test cases.
The first line of each test case contains two integers, ‘N’ and ‘M’, denoting the number of levels and the number of difficulty modes respectively.
Each of the next ‘N’ lines contains ‘M’ single space-separated integers, elements of 2D array ‘POINTS’.
Output format :
Return the maximum score that can be obtained on completion of the game.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 100
1 <= N, M <= 100
1 <= POINTS[i][j] <= 100
Time Limit: 1 sec
Approaches
In this approach, we will recursively try out all possible combinations of levels and difficulty modes. A recursive function is called with every difficulty mode for the first level and for the subsequent levels we will try all possible difficulty modes and will choose the one with the maximum score.
At max we will be having three choices at each level which are playing the next level on the same difficulty mode, one mode above, or one mode lower than the current one.
When the ‘LEVEL’ parameter of the recursive function (denoting the current level of the game) crosses the last level we will return zero.
The steps are as follows:-
// Recursive function to find maximum score
function getMaxScoreUtil(int level, int difficulty, int n, int m, [ [ int ] ] points):
- If ‘LEVEL’ is equal to N.
- Return 0.
- Initialize the variable ‘ANS’.
- Call the function getMaxScoreUtil with LEVEL = LEVEL+1 and the same ‘DIFFICULTY’ and store the returned value in ANS.
- If the value of ‘DIFFICULTY’ > 0.
- Call the function getMinIngredirentsUtil with LEVEL = LEVEL +1 and DIFFICULTY = DIFFICULTY -1.
- Update the value of ANS with the maximum of ANS and the value returned by the above function call.
- If the value of ‘DIFFICULTY’ < ‘M-1’.
- Call the function getMinIngredirentsUtil with LEVEL = LEVEL +1 and DIFFICULTY = DIFFICULTY +1.
- Update the value of ANS with the maximum of ANS and the value returned by the above function call.
- Return the value ANS + POINTS[ ‘LEVEL’ ][ ‘DIFFICULTY’ ].
function getMaxScore(int n, int m, [ [ int ] ] points):
- Initialize a variable ‘ANS’ with 0, denoting the maximum score a player can get.
- Run a for loop from i = 0…M-1
- Call the function getMaxScoreUtil with ‘LEVEL’ = 0 and ‘DIFFICULTY’ = i.
- Update the value of ANS with the maximum of ANS and the value returned by the above function call.
- Return the value of the variable 'ANS'.
The recursive approach discussed before can be optimized using memoization. We can memoize the result for each state with a particular ‘LEVEL’ and ‘DIFFICULTY’. In this way, we can save time from recalculating the already calculated results.
For memoization let us define a matrix 2-dimensional array ‘DP’ of size ‘N’ x ‘M’.
DP[i][j] - Maximum score that can be obtained if the game starts from the ith level in jth difficulty mode.
The steps are as follows:-
// Recursive function to find maximum score
function getMaxScoreUtil(int level, int difficulty, int n, int m, [ [ int ] ] points, [ [ int ] ] dp):
- If ‘LEVEL’ is equal to N.
- Return 0.
- If DP[ LEVEL ][ DIFFICULTY ] is not equal to -1.
- Return the value of DP[ LEVEL ][ DIFFICULTY ].
- Initailze the variable ‘ANS’.
- Call the function getMaxScoreUtil with LEVEL = LEVEL+1 and the same ‘DIFFICULTY’ and store the returned value in ANS.
- If the value of ‘DIFFICULTY’ > 0.
- Call the function getMinIngredirentsUtil with LEVEL = LEVEL +1 and DIFFICULTY = DIFFICULTY -1.
- Update the value of ANS with the maximum of ANS and the value returned by the above function call.
- If the value of ‘DIFFICULTY’ < ‘M-1’.
- Call the function getMinIngredirentsUtil with LEVEL = LEVEL +1 and DIFFICULTY = DIFFICULTY +1.
- Update the value of ANS with the maximum of ANS and the value returned by the above function call.
- DP[ LEVEL ][ DIFFICULTY ] = ANS + POINTS[ ‘LEVEL’ ][ ‘DIFFICULTY’ ].
- Return the value of DP[ LEVEL ][ DIFFICULTY ].
function getMaxScore(int n, int m, [ [ int ] ] points):
- Initialize a variable ‘ANS’ with 0, denoting the maximum score a player can get.
- Initialize 2D array ‘DP’ of dimension N * M with -1
- Run a for loop from i = 0…M-1
- Call the function getMaxScoreUtil with ‘LEVEL’ = 0 and ‘DIFFICULTY’ = i.
- Update the value of ANS with the maximum of ANS and the value returned by the above function call.
- Return the value of the variable 'ANS’.
The idea is the same as memoization. We are going to use the recurrence relation:
DP[i][j] = POINTS[i][j] + min( DP[i+1][j-1], DP[i+1][j], DP[i+1][j+1]). If the difficulty mode mentioned in the recurrence exists in the next level then take that value otherwise take 0.
DP[i][j] - Maximum score that can be obtained if the game starts from the ith level in jth difficulty mode.
The steps are as follows:-
function getMaxScore(int n, int m, [ [ int ] ] points):
- Initialize a variable ‘ANS’ with 0, denoting the maximum score a player can get.
- Initialize 2D array ‘DP’ of dimension N * M.
- Run a for loop from i =0…M-1:
- Assign DP[N-1][i] = POINTS[N-1][i].
- Run a for loop from i=N-2….0.
- Run a for loop from j=0….M-1
- DP[i][j] = DP[i+1][j].
- If the value of j > 0:
- Update the value of DP[i][j] with the maximum of DP[i][j] and DP[i+1][j-1].
- If the value of j < M-1:
- Update the value of DP[i][j] with the maximum of DP[i][j] and DP[i+1][j+1].
- Add POINTS[i][j] to DP[i][j].
- Run a for loop from j=0….M-1
- Run a for loop from i = 0…M-1
- Update the value of ANS with the maximum of ANS and DP[0][i].
- Return the value of ‘ANS’ variable.