CODEWITHSUNDEEP
javaalgorithmdebuggingrecursioniteration
randomUser47534
randomUser47534

Reputation: 329

Recursive stair climbing algorithm

I am trying to change the following algorithm from recursive to iterative, and am having problems doing so. (Book: "Cracking the Coding Interview.")

Question: "A child is running up a staircase with n steps, and can hop either 1, 2, or 3 steps at a time. Implement a method to count how many ways the child can run up the stairs."

Book's answer (recursive):

public static int countWays(int n, int[] map) {

    if (n < 0)
        return 0;
    if (n == 0)
        return 1;
    if (map[n] > -1)
        return map[n];

    map[n] = countWays(n - 1, map) + countWays(n - 2, map) + countWays(n - 3, map);

    return map[n];

}

My answer (iterative):

public static int countWays(int n, int[] map) {

    for (int i = 1; i <= n; i++) {

        //Problem with writing it this way: index could be negative
        map[i] = map[i - 1] + map[i - 2] + map[i - 3];

    }

    return map[n];

}

One problem I am having with my given answer is that the line "map[i - 1] + map[i - 2] + map[i - 3]" could result in negative indices, which would throw an error.

There may be other problems with my code.

Could someone please help in writing this?

Upvotes: 0

Views: 2146

Answers (4)

ronn164
ronn164

Reputation: 21

The iterative approach you are using is called bottom-up dynamic programming. It is different from top-down recursion with memoization. Bottom-up is more efficient because you are avoiding the stack overhead associated with recursion.

Steps:
1 -> 1 = 1 way
2 -> 11, 2 = 2 ways
3 -> 111, 12, 21, 3 = 4 ways
4 -> 1111, 112, 121, 211, 22, 31, 31 = 7 ways

Another way to get around your index problem is to create an array with a minimal size of 3 and start from the 3rd index. You're using a little more space but it simplifies your code.

public int countWaysDP(int n) {
    if (n < 0) {
        throw new IllegalArgumentException();
    }
    int[] dp = new int[Math.max(3, n)];
    dp[0] = 1; // 1
    dp[1] = 2; // 11, 2
    dp[2] = 4; // 111, 12, 21, 3
    for (int i = 3; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];    
    }
    return dp[n - 1];
}

Hope this helps your training.

Upvotes: 2

Shobhit_Geek
Shobhit_Geek

Reputation: 599

public static int countWays(int n, int[] map) {

   if(n == 0 || n==1)
     return 1;
   if(n == 2)
     return 2;
   map[0] = 1;
   map[1] = 1;
   map[2] = 2;
   for (int i = 3; i <= n; i++) {

       //Problem with writing it this way: index could be negative
       map[i] = map[i - 1] + map[i - 2] + map[i - 3];

   }

return map[n];

}

Upvotes: 1

Edward J Beckett
Edward J Beckett

Reputation: 5140

Since this is clearly a coding interview question... I'm going to show you a similar solution to review, In Scala, to help you learn the fundamentals.

import scala.annotation.tailrec

object Main {

/**
 * Count ways to make change...
 */
 def countChange(money: Int, coins: List[Int]): Int = {
    def reduce(money: Int, coins: List[Int]): Int ={
      if (money == 0) 1
      else if (money < 0 || coins.isEmpty) 0
      else reduce(money - coins.head, coins) + reduce(money, coins.tail)
    }
    reduce(money, coins)
  }
}

Upvotes: 0

Adam Evans
Adam Evans

Reputation: 2082

Hardcode the first index to have a value of 1, then put each term of the sum in its own if statement to check for a negative index. If the index is negative, don't include it in the sum.

Alternatively, you could just hardcode the first three values, then start at 4 and not worry about it.

Upvotes: 1

Related Questions