Mario And His Princess

There are ‘N’ dragons on the road and for each dragon, we have two choices either we take the diamond from him or we don’t take the diamond from him. We can not take DIAMOND from two successive dragons so have to make sure of that as well.

Initially, we have 0 DIAMOND and for each ‘i’ from 0 to ‘N’-1 (0-based indexing), we can take DIAMOND from the current dragon if we haven’t taken DIAMOND from the direct previous dragon of the current dragon if there are any, and for that, we will make a flag which we will make false when we take the DIAMOND and we take diamond if the flag is true and if we don’t take the diamond than make the flag true and call for the next index and return the max of the cases where we took the DIAMOND from the current dragon and we didn’t take the diamond from the current dragons.

The Steps are as follows:-

maxDiamondRec( i:int, flag:bool, DIAMOND:[], currSum:[] ):

1. Create a variable denoting size of the array.
2. If we are out the index of the array. Return currSum.
3. Check the answer if we don't take the current element.
4. As we are not taking the current element so we can take the next element so make the flag value high Store it in x.
5. Create another variable y with an initial value equal to zero.
6. Check if we can take the diamond from the current dragon. If Yes then take the diamond from the current dragon and set the flag to false as we can't take the diamond from the Next successive dragon.
7. Return the max of x,y.

diamondForPrincess( diamond )

1. Call the maxDiamondRec function with current index(i) = 0, flag = true, currSum = 0.

If there are ‘N’ dragons and we want to take the maximum number of DIAMOND then if we closely look, We can take the maximum number of DIAMOND from ‘N’ dragons by taking a maximum of the following 2:-

1. Either we take the diamond from the ‘N’th dragon then we can not take DIAMOND from (N-1)th dragon but we can take the maximum number of DIAMOND from (N-2) dragons so the total will be:
   • Diamond from the Nth dragon + Max DIAMOND we can get the first N-2 dragons.
2. We take max DIAMOND from the first N-1 dragons and don’t take DIAMOND from the current dragon.

Now the base case will be when there is 0 dragon then we can not take any diamond and where there is only 1 dragon then we can take the DIAMOND from that dragon only and then we can use the above approach for all the dragons till ‘N’. The only problem here is we are calculating the same thing over and over again so we can store the answer in a DP array when it is first called then on another call we will directly return it from the DP array.

The Steps are as follows:-

maxDiamondRec( i, DIAMOND, DP )

1. Create a variable denoting size of the array.
2. Base Case, If we are out the index of the array means i<0. Return 0 as we can not any DIAMOND.
3. f the value for the current index is already memoized in the DP, Then return the answer from there.
4. Currently, we take the diamond from the current dragon then we can not take the diamond from the next dragon.
5. Also if we take the max diamond from the next dragon (i-2)th dragons then we cannot take DIAMOND from (i-3)th dragon. So we will take the diamond from the max of (i-2) or (i-3) dragon which will look something like this:-
   • diamond[i]+max(maxDiamondRec(i-2,diamond,DP),maxDiamondRec(i-3,diamond,DP))
6. Store it in DP[i] and return the value of DP[i].
    

diamondForPrincess( diamond, n )

1. Declare a variable 'n' denoting the size of the current number of dragons.
2. Create a DP array initialized with -1 of size (n+1).
3. If we take a diamond from the (n-1)th dragon then we can not take a diamond from the (n-2)th one and vice versa.
4. We will take the diamond from the max of both of them and store it in 'ans' by calling the function :-
   • maxDiamondRec( n-1, diamond,DP),maxDiamondRec(n-2,diamond,DP)
5. Return 'ans'.

If there are ‘N’ dragons and we want to take the maximum number of DIAMOND then if we closely look, We can take the maximum number of DIAMOND from ‘N’ dragons by taking a maximum of the following:-

1. Either we take the diamond from the ‘N’th dragon then we can not take DIAMOND from (N-1)th dragon but we can take the maximum number of DIAMOND from (N-2) dragons so the total will be:
   • Diamond from the Nth dragon + Max DIAMOND we can get the first N-2 dragons.
2. We take max DIAMOND from the first N-1 dragons and don’t take DIAMOND from the current dragon.
3. Now the base case will be when there is 0 dragon then we can not take any diamond and where there is only 1 dragon then we can take the DIAMOND from that dragon only and then we can use the above approach for all the dragons till ‘N’ in a bottom-up manner.

The Steps are as follows:-

diamondForPrincess( diamond )

1. Create a DP array of the size number of dragons+1.
2. Set DP[0] = 0.
3. Set DP[1] = DIAMOND at 1 dragon.
4. If the number of dragons is 1.
   • Return the diamond from the only dragon.
5. Now for each dragon from 2 to n.
   • The max DIAMOND we can get from first i dragons are:-
   • Either We take max DIAMOND from the i-1 dragons or we can take DIAMOND from the current dragon and max DIAMOND from the i-2 dragons we take the max of these two cases.
6. Return the value of DP[N].