Count number of ways to cover a distance

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(intdistance) {

           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);

     }

}