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$ Commented Jun 11, 2018 at 20:31
  • $\begingroup$ You can solve this using recursion. $\endgroup$ Commented Jun 11, 2018 at 20:31
  • $\begingroup$ I have the solution using recursion already. Thank you. $\endgroup$
    – Maxfield
    Commented Jun 11, 2018 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$ Commented Jun 11, 2018 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
    Commented Jun 12, 2018 at 4:25

2 Answers 2

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
    Commented Jan 3, 2021 at 21:50
  • $\begingroup$ What do you think? What would make sense? $\endgroup$ Commented Jan 3, 2021 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
    Commented Jan 3, 2021 at 21:54
  • $\begingroup$ Try it out and see what you get. $\endgroup$ Commented Jan 3, 2021 at 21:54
  • 1
    $\begingroup$ Yes, that’s the idea. $\endgroup$ Commented Jan 4, 2021 at 6:32
0
$\begingroup$

I was thinking same so I solved with python but in my question there were three step constrain instead of 2

def paths(n):
    if n==0:
        empty = []
        empty.append('')
        return empty
    if n<0:
        empty = []
        return empty
    
    paths1 = paths(n-1)
    paths2 = paths(n-2)
    paths3 = paths(n-3)
    
    path = []
    for i in paths1:
        path.append(i+'1')
    for i in paths2:
        path.append(i+'2')
    for i in paths3:
        path.append(i+'3')
    return path
$\endgroup$
1
  • 1
    $\begingroup$ Hello at COMPUTER SCIENCE @SE. Please state, in a single question sentence, what your post answers. Check if that sums up Maxfield's 2018 question. $\endgroup$
    – greybeard
    Commented Aug 3, 2021 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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