Question

This is a dynamic programming problem. Please follow the guideline given above to solve the problem. Thanks.

2. Super Mario must travel through a landscape made up of n spaces each filled with a mushroom, a spike or nothing. He wishes to reach the princess who is on space n. Super Mario can choose to advance ALT step or jump J steps. To start, J-2, if he lands on a space that has a mushroom then J increases by You are given an array of the landscape L[L , n] such that L[i] = N if there is nothing on space i, LiM if there is a mushroom on space i and L-S if there is a spike on space i. Design an algorithm that returns the minimum number of actions needed (jump or advance) for Super Mario to reach space n without hitting a spike. 1: Define the sub-problems and corresponding array 3: the recursion used to fill the array and a case analysis that explains the recursion 4: ordering of the subproblems 5: final form of output 6: pseudocode (optional 7: time analysis

Answer 1

In the given problem we have to calculate the minimum number of actions needed to reach index 'N' in the array by Super Mario.

Let's assume we know the answer for every index less than or equal to 'i' that means we know the minimum number of actions needed to any index before i+1.

Since it can be clearly seen that Super Mario can reach position 'i+1' from somewhere which has index less than 'i+1' either by jumping some steps or by advancing.

i-2 i-1i 2 4

let's f(i,j) denotes the answer of the problem up to index 'i' where super Mario has reached by taking the previous jump of 'j' steps.

Let's see the different cases:

Case: 1

If L[i] = N,

for ( j = 1 to j = i )

f ( i, j ) = f ( i, j ) + 1;

Case: 2

  if L[i] = M,

for ( j = 1 to j = i )

f ( i, j+1 ) = f ( i, j ) + 1;

Case: 3

if L[i] = S,

for ( j=1 to j = i )

f ( i, j-1 ) = f ( i, j ) + 1;

BASE CASES:

We have to initialise f( i,j ) = INF, for all possible values of i, j

where INF is a very large integer.

since initially J = 2, and super Mario can also advance. f ( 0, 1 ) = 0, f ( 0, 2) = 0;

FINAL FORM OF OUTPUT:

Since as per given we want to finally reach 'N' index, our answer to the problem will be minimum possible value for all possible value of 'j's.

for ( j =1 to j = N)

actual_ans = min(actual_ans, f(N, j) ) ;

PSUEDO CODE:

let dp[1.2,3...n,1,2,3..n] be a new 2d table of n*n dimension

for( i = 1 to i = N)

for (j = 1 to j = i)

dp[i][j] = INF;

dp[0][1] = 0, dp[0][2] = 0;

for( i = 1 to i = N )

for ( j = 1 to j = i )

if L[i] == N

dp[i][j] = dp[i][i-j] + 1;

if L[i] == M

dp[i][j+1] = dp[i][i-j] +1;

if L[i] == S

dp[i][j-1] = dp[i][i-j]+1;

dp[i][j] = max ( dp[i][j], INF); // for surity of not crossing infinte value

integer ans;

ans = INF;

for ( i = 0 to i = N)

ans = min( ans, dp[N][i] );

TIME COMPLEXITY ANALYSIS

It is obvious from the pseudo code that there is a concatenation of two for loops which in worst case runs up to N steps.

i.e time complexity is    
O(n2)
.