Count total number of ways to cover the distance with
1, 2 and 3 steps.

Recursion solution time complexity is exponential i.e. O(3n).

Since same sub problems are solved again, this problem
has overlapping sub problems property. So min square sum problem has both
properties of a dynamic programming problem.

public class MaxStepsCount {

**/** Dynamic Programming. */**

**private**

**static**

**int**

**getMaxWaysDP(**

**int**

**distance**

**) {**

**int**

**[]**

**count**

**=**

**new**

**int**

**[**

**distance**

**+1];**

**count**

**[0] = 1;**

**count**

**[1] = 1;**

**count**

**[2] = 2;**

**/** Memorize the Sub**

**-**

**problem in bottom up manner*/**

**for**

**(**

**int**

**i**

**=3;**

**i**

**<=**

**distance**

**;**

**i**

**++) {**

**count**

**[**

**i**

**] =**

**count**

**[**

**i**

**-1] +**

**count**

**[**

**i**

**-2] +**

**count**

**[**

**i**

**-3];**

**}**

**return**

**count**

**[**

**distance**

**];**

**}**

/** Recursion Approach. */

private static int getMaxWaysRecur(int
distance) {

if(distance<0) {

return 0;

} else if(distance==0) {

return 1;

}

return getMaxWaysRecur(distance-1)+getMaxWaysRecur(distance-2)

+getMaxWaysRecur(distance-3);

}

public static void main(String[] args) {

// Steps pf 1, 2 and 3.

int distance = 10;

/** Recursion Approach. */

int ways = getMaxWaysRecur(distance);

System.

*out*.println(ways);
/** Dynamic Programming. */

ways =

*getMaxWaysDP*(distance);
System.

*out*.println(ways);
}

}

## No comments:

## Post a Comment