Geek Answers Handbook

Find all the ways in which you can climb the n step ladder if you can take k steps at a time, so k <= n

This is a problem that I am trying to solve on my own in order to improve recursion a bit (rather than homework). I believe that I have found a solution, but I'm not sure about the complexity of the time (I know that DP will give me better results).

Find all the ways in which you can climb the n step ladder if you can take k steps at a time, so k <= n

For example, if the step size is [1,2,3], and the stairwell is 10, I could perform 10 steps of size 1 [1,1,1,1,1,1,1,1, 1,1,1] = 10 or I could do 3 steps of size 3 and 1 step of size 1 [3,3,3,1] = 10

Here is my solution:

 static List<List<Integer>> problem1Ans = new ArrayList<List<Integer>>(); public static void problem1(int numSteps){ int [] steps = {1,2,3}; problem1_rec(new ArrayList<Integer>(), numSteps, steps); } public static void problem1_rec(List<Integer> sequence, int numSteps, int [] steps){ if(problem1_sum_seq(sequence) > numSteps){ return; } if(problem1_sum_seq(sequence) == numSteps){ problem1Ans.add(new ArrayList<Integer>(sequence)); return; } for(int stepSize : steps){ sequence.add(stepSize); problem1_rec(sequence, numSteps, steps); sequence.remove(sequence.size()-1); } } public static int problem1_sum_seq(List<Integer> sequence){ int sum = 0; for(int i : sequence){ sum += i; } return sum; } public static void main(String [] args){ problem1(10); System.out.println(problem1Ans.size()); }

I assume that this is the runtime k ^ n, where k is the number of step sizes and n is the number of steps (in this case 3 and 10).

I came to this answer because each step size has a loop that causes k number of steps. However, the depth of this is not the same for all step sizes. For example, the sequence [1,1,1,1,1,1,1,1,1,1,1,1,1] has more recursive calls than [3,3,3,1], so it makes me doubt my answer .

What is the lead time? Is k ^ n correct?

+5
source share
2 answers

TL DR: your algorithm is O (2 n ), which is a tougher estimate than O (k n ), but due to some easily corrected inefficiencies, the implementation is done in O (k 2 x 2 n ).

Essentially, your solution lists all the sequence of steps with the sum n by sequentially listing all the viable prefixes of these step sequences. Thus, the number of operations is proportional to the number of step sequences whose sum is less than or equal to n . [Cm. Notes 1 and 2].

Now consider how many possible prefix sequences exist for a given value of n . The exact calculation will depend on the steps allowed in the step size vector, but we can easily get the maximum, because any sequence of steps is a subset of the set of integers from 1 to n , and we know that there are exactly 2 n such subsets.

Of course, not all subsets qualify. For example, if the set of step sizes is [1, 2] , then you list Fibonacci sequences, and there are O (? Ph ) such sequences. As k increases, you get closer and closer to O (2 n ). [Note 3]

Due to the inefficiency of your code, as already noted, your algorithm is actually O (k 2 ? Alpha), where? is a number between & phis; and 2, approaching 2 when k approaches infinity. (? ph. 1,618 ... or (1 + sqrt (5)) / 2)).

There are a number of improvements that can be made to your implementation, especially if your intention was to count, rather than enumerate step sizes. But that was not your question, as I understand it.

Notes

  • This is not entirely accurate, because you are actually listing a few additional sequences that you then reject; the cost of these failures is a factor in the size of the vector of possible step sizes. However, you can easily eliminate the deviations by completing the for loop as soon as the deviation is detected.

  • The cost of an enumeration is O (k), not O (1), because you calculate the sum of the sequence arguments for each enumeration (often twice). This gives an additional coefficient k . You can easily eliminate this cost by passing the current amount into a recursive call (which will also eliminate multiple estimates). It is far more likely to avoid the cost of O (k) copying the sequence to the output list, but this can be done using a more efficient data structure.

  • The question in your title (as opposed to the problem solved by the code in the body of your question) really requires an enumeration of all possible subsets of {1 & hellip; n}, and in this case the number of possible sequences will be exactly 2 n .

+1
source

If you want to solve this problem recursively, you should use another template that allows you to cache previous values, for example, used in calculating Fibonacci numbers. The code for the Fibonacci function is basically the same as you, it adds the previous and previous numbers in the index and returns the result as the current number. You can use the same technique in your recursive function, but do not add f (k-1) and f (k-2), but collect the sum of f (k-steps [i]). Something like this (I don't have Java syntax checking, so please be with syntax errors):

 static List<Integer> cache = new ArrayList<Integer>; static List<Integer> storedSteps=null; // if used with same value of steps, don't clear cache public static Integer problem1(Integer numSteps, List<Integer> steps) { if (!ArrayList::equal(steps, storedSteps)) { // check equality data wise, not link wise storedSteps=steps; // or copy with whatever method there is cache.clear(); // remove all data - now invalid // TODO make cache+storedSteps a single structure } return problem1_rec(numSteps,steps); } private static Integer problem1_rec(Integer numSteps, List<Integer> steps) { if (0>numSteps) { return 0; } if (0==numSteps) { return 1; } if (cache.length()>=numSteps+1) { return cache[numSteps] } // cache hit Integer acc=0; for (Integer i : steps) { acc+=problem1_rec(numSteps-i,steps); } cache[numSteps]=acc; // cache miss. Make sure ArrayList supports inserting by index, otherwise use correct type return acc; }
+1
source

More articles:


All Articles