2
$\begingroup$

I came across this classic question and found may many solution to it. for loop and DP/ reclusive + memorization.

Also found a twisted version of the questions asking to print all possible path instead of counting. Wondering for the twisted version, if we have DP solution ?
Q: If there are n stairs, you can either take 1 or 2 steps at a time, how may way can you finish the stairs. we can just using fib to calculate it. What if you are ask print out all possible ways(not revision please). For example, if n = 5. we have as solution. pseudo code is welcome.

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 2, 1, 1]
[1, 2, 2]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1] 
$\endgroup$
6
  • $\begingroup$ Java-specific questions are off-topic here. $\endgroup$ – Yuval Filmus Jun 11 '18 at 20:31
  • $\begingroup$ You can solve this using recursion. $\endgroup$ – Yuval Filmus Jun 11 '18 at 20:31
  • $\begingroup$ I have the solution using recursion already. Thank you. $\endgroup$ – Maxfield Jun 11 '18 at 20:49
  • 1
    $\begingroup$ So what is missing? Dynamic programming doesn't really work here, since you want to list all solutions. There are no savings to be had. $\endgroup$ – Yuval Filmus Jun 11 '18 at 22:01
  • $\begingroup$ ok, I am trying to improve the performance since the untwisted question(only count) can solved in O(n) time. Wondering if we can do the same for this it. Thank you. $\endgroup$ – Maxfield Jun 12 '18 at 4:25
1
$\begingroup$

Here is pseudocode for solving this, using a recursive procedure:

All-Solutions($n$):

If $n=0$, return the solution (empty sequence).

If $n=1$, return the solution $1$.

Otherwise:

  1. Run All-Solutions($n-1$), and prefix $1$ to all results.

  2. Run All-Solutions($n-2$), and prefix $2$ to all results.


There is also a simple iterative solution. Start with the solution composed of $n$ many $1$s, and iteratively try to increase it, until getting stuck. How to increase a solution?

  • If a solution ends with $1,1$, replace this with $2$.
  • If a solution ends with $2,1$, consider the suffix of the form $1,2,\ldots,2,1$; if none exists, then the process terminates. If the suffix contains $\ell$ many $2$s, replace it with $2$ followed by $2\ell$ many $1$s.
  • If a solution ends with $2$, consider the suffix of the form $1,2,\ldots,2$; if none exists, then the process terminates. If the suffix contains $\ell$ many $2$s, replace it with $2$ followed by $2\ell-1$ many $1$s.

Here is an example, $n=5$: \begin{align} &1,1,1,1,1 \\ &1,1,1,2 \\ &1,1,2,1 \\ &1,2,1,1 \\ &1,2,2 \\ &2,1,1,1 \\ &2,1,2 \\ &2,2,1 \end{align}

Both solutions output the list in lexicographic order. The iterative one has $O(1)$ amortized update time. Indeed, the length of the list is $F_{n+1}$, and the total length of suffixes is $F_{n+3}-2$, and so the average length of a suffix is roughly $\phi^2 = \phi + 1 \approx 2.618$.

$\endgroup$
10
  • $\begingroup$ Do we need to prefix 1 and 2 to the solutions in each function call? I $\endgroup$ – a_sid Jan 3 at 21:50
  • $\begingroup$ What do you think? What would make sense? $\endgroup$ – Yuval Filmus Jan 3 at 21:51
  • $\begingroup$ I do NOT think it should happen in each function call. I think we should prefix 1 and 2 after we have returned to the ultimate/1st function call with all the values. $\endgroup$ – a_sid Jan 3 at 21:54
  • $\begingroup$ Try it out and see what you get. $\endgroup$ – Yuval Filmus Jan 3 at 21:54
  • 1
    $\begingroup$ Yes, that’s the idea. $\endgroup$ – Yuval Filmus Jan 4 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.