Finding all paths down stairs?

问题:

I was given the following problem in an interview:

Given a staircase with N steps, you can go up with 1 or 2 steps each time. Output all possible way you go from bottom to top.

For example:

N = 3

Output :
1 1 1
1 2
2 1

When interviewing, I just said to use dynamic programming.

S(n) = S(n-1) +1 or S(n) = S(n-1) +2

However, during the interview, I didn't write very good code for this. How would you code up a solution to this problem?

Thanks indeed!

回答1:

You can generalize your recursive function to also take already made moves.

void steps(n, alreadyTakenSteps) {
    if (n == 0) {
        print already taken steps
    }
    if (n >= 1) {
        steps(n - 1, alreadyTakenSteps.append(1));
    }
    if (n >= 2) {
        steps(n - 2, alreadyTakenSteps.append(2));
    }
}

It's not really the code, more of a pseudocode, but it should give you an idea.

回答2:

I won't write the code for you (since it's a great exercise), but this is a classic dynamic programming problem. You're on the right track with the recurrence; it's true that

S(0) = 1

Since if you're at the bottom of the stairs there's exactly one way to do this. We also have that

S(1) = 1

Because if you're one step high, your only option is to take a single step down, at which point you're at the bottom.

From there, the recurrence for the number of solutions is easy to find. If you think about it, any sequence of steps you take either ends with taking one small step as your last step or one large step as your last step. In the first case, each of the S(n - 1) solutions for n - 1 stairs can be extended into a solution by taking one more step, while in the second case each of the S(n - 2) solutions to the n - 2 stairs case can be extended into a solution by taking two steps. This gives the recurrence

S(n) = S(n - 2) + S(n - 1)

Notice that to evaluate S(n), you only need access to S(n - 2) and S(n - 1). This means that you could solve this with dynamic programming using the following logic:

1. Create an array S with n + 1 elements in it, indexed by 0, 1, 2, ..., n.
2. Set S[0] = S[1] = 1
3. For i from 2 to n, inclusive, set S[i] = S[i - 1] + S[i - 2].
4. Return S[n].

The runtime for this algorithm is a beautiful O(n) with O(n) memory usage.

However, it's possible to do much better than this. In particular, let's take a look at the first few terms of the sequence, which are

 S(0) = 1
 S(1) = 1
 S(2) = 2
 S(3) = 3
 S(4) = 5

This looks a lot like the Fibonacci sequence, and in fact you might be able to see that

 S(0) = F(1)
 S(1) = F(2)
 S(2) = F(3)
 S(3) = F(4)
 S(4) = F(5)

This suggests that, in general, S(n) = F(n + 1). We can actually prove this by induction on n as follows.

As our base cases, we have that

S(0) = 1 = F(1) = F(0 + 1)

and

S(1) = 1 = F(2) = F(1 + 1)

For the inductive step, we get that

S(n) = S(n - 2) + S(n - 1) = F(n - 1) + F(n) = F(n + 1)

And voila! We've gotten this series written in terms of Fibonacci numbers. This is great, because it's possible to compute the Fibonacci numbers in O(1) space and O(lg n) time. There are many ways to do this. One uses the fact that

F(n) = (1 / √(5)) (Φⁿ + φⁿ)

Here, Φ is the golden ratio, (1 + √5) / 2 (about 1.6), and φ is 1 - Φ, about -0.6. Because this second term drops to zero very quickly, you can get a the nth Fibonacci number by computing

(1 / √(5)) Φⁿ

And rounding down. Moreover, you can compute Φⁿ in O(lg n) time by repeated squaring. The idea is that we can use this cool recurrence:

x⁰ = 1

x²ⁿ = xⁿ * xⁿ

x^{2n + 1} = x * xⁿ * xⁿ

You can show using a quick inductive argument that this terminates in O(lg n) time, which means that you can solve this problem using O(1) space and O(lg n) time, which is substantially better than the DP solution.

Hope this helps!

回答3:

Great answer by @templatetypedef - I did this problem as an exercise and arrived at the Fibonacci numbers on a different route:

The problem can basically be reduced to an application of Binomial coefficients which are handy for Combination problems: The number of combinations of n things taken k at a time (called n choose k) can be found by the equation

Given that and the problem at hand you can calculate a solution brute force (just doing the combination count). The number of "take 2 steps" must be zero at least and may be 50 at most, so the number of combinations is the sum of C(n,k) for 0 <= k <= 50 ( n= number of decisions to be made, k = number of 2's taken out of those n)

BigInteger combinationCount = 0;
for (int k = 0; k <= 50; k++)
{
    int n = 100 - k;
    BigInteger result = Fact(n) / (Fact(k) * Fact(n - k));
    combinationCount += result;
}

The sum of these binomial coefficients just happens to also have a different formula:

回答4:

Your solution sounds right.

S(n):
    If n = 1 return {1}
    If n = 2 return {2, (1,1)}
    Return S(n-1)x{1} U S(n-2)x{2}

(U is Union, x is Cartesian Product)

Memoizing this is trivial, and would make it O(Fib(n)).

回答5:

Actually, you can prove that the number of ways to climb is just the fibonacci sequence. Good explanation here: http://theory.cs.uvic.ca/amof/e_fiboI.htm

回答6:

Solving the problem, and solving it using a dynamic programming solution are potentially two different things.

http://en.wikipedia.org/wiki/Dynamic_programming

In general, to solve a given problem, we need to solve different parts of the problem (subproblems), then combine the solutions of the subproblems to reach an overall solution. Often, many of these subproblems are really the same. The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations

This leads me to believe you want to look for a solution that is both Recursive, and uses the Memo Design Pattern. Recursion solves a problem by breaking it into sub-problems, and the Memo design pattern allows you to cache answers, thus avoiding re-calculation. (Note that there are probably cache implementations that aren't the Memo design pattern, and you could use one of those as well).

Solving:

The first step I would take would be to solve some set of problems by hand, with varying or increasing sizes of N. This will give you a pattern to help you figure out a solution. Start with N = 1, through N = 5. (as others have stated, it may be a form of the fibbonacci sequence, but I would determine this for myself before calling the problem solved and understood).

From there, I would try to make a generalized solution that used recursion. Recursion solves a problem by breaking it into sub-problems.

From there, I would try to make a cache of previous problem inputs to the corresponding output, hence memoizing it, and making a solution that involved "Dynamic Programming".

I.e., maybe the inputs to one of your functions are 2, 5, and the correct result was 7. Make some function that looks this up from an existing list or dictionary (based on the input). It will look for a call that was made with the inputs 2, 5. If it doesn't find it, call the function to calculate it, then store it and return the answer (7). If it does find it, don't bother calculating it, and return the previously calculated answer.

回答7:

Here is a simple solution to this question in very simple CSharp (I believe you can port this with almost no change to Java/C++). I have added a little bit more of complexity to it (adding the possibility that you can also walk 3 steps). You can even generalize this code to "from 1 to k-steps" if desired with a while loop in the addition of steps (last if statement).

I have used a combination of both dynamic programming and recursion. The use of dynamic programming avoid the recalculation of each previous step; reducing the space and time complexity related to the call stack. It however adds some space complexity (O(maxSteps)) which I think is negligible compare to the gain.

/// <summary>
/// Given a staircase with N steps, you can go up with 1 or 2 or 3 steps each time.
/// Output all possible way you go from bottom to top
/// </summary>
public class NStepsHop
{
    const int maxSteps = 500;  // this is arbitrary
    static long[] HistorySumSteps = new long[maxSteps];

    public static long CountWays(int n)
    {
        if (n >= 0 && HistorySumSteps[n] != 0)
        {
            return HistorySumSteps[n];
        }

        long currentSteps = 0;
        if (n < 0)
        {
            return 0;
        }
        else if (n == 0)
        {
            currentSteps = 1;
        }
        else
        {
            currentSteps = CountWays(n - 1) + 
                           CountWays(n - 2) + 
                           CountWays(n - 3);
        }

        HistorySumSteps[n] = currentSteps;
        return currentSteps;
    }
}

You can call it in the following manner

long result;
result = NStepsHop.CountWays(0);    // result = 1
result = NStepsHop.CountWays(1);    // result = 1
result = NStepsHop.CountWays(5);    // result = 13
result = NStepsHop.CountWays(10);   // result = 274
result = NStepsHop.CountWays(25);   // result = 2555757

You can argue that the initial case when n = 0, it could 0, instead of 1. I decided to go for 1, however modifying this assumption is trivial.

回答8:

the problem can be solved quite nicely using recursion:

void printSteps(int n)
{
   char* output = new char[n+1];
   generatePath(n, output, 0);
   printf("\n");
}

void generatePath(int n, char* out, int recLvl)
{
   if (n==0)
   {
      out[recLvl] = '\0';
      printf("%s\n",out);
   }

   if(n>=1)
   {
      out[recLvl] = '1';
      generatePath(n-1,out,recLvl+1);
   }

   if(n>=2)
   {
      out[recLvl] = '2';
      generatePath(n-2,out,recLvl+1);
   }
}

and in main:

void main()
{
    printSteps(0);
    printSteps(3);
    printSteps(4);
    return 0;       
}

回答9:

It's a weighted graph problem.

• From 0 you can get to 1 only 1 way (0-1).
• You can get to 2 two ways, from 0 and from 1 (0-2, 1-1).
• You can get to 3 three ways, from 1 and from 2 (2 has two ways).
• You can get to 4 five ways, from 2 and from 3 (2 has two ways and 3 has three ways).
• You can get to 5 eight ways, ...

A recursive function should be able to handle this, working backwards from N.

回答10:

Complete C-Sharp code for this

 void PrintAllWays(int n, string str) 
    {
        string str1 = str;
        StringBuilder sb = new StringBuilder(str1);
        if (n == 0) 
        {
            Console.WriteLine(str1);
            return;
        }
        if (n >= 1) 
        {
            sb = new StringBuilder(str1);
            PrintAllWays(n - 1, sb.Append("1").ToString());
        }
        if (n >= 2) 
        {
            sb = new StringBuilder(str1);
            PrintAllWays(n - 2, sb.Append("2").ToString());
        }
    }

回答11:

Late C-based answer

#include <stdio.h>
#include <stdlib.h>
#define steps 60
static long long unsigned int MAP[steps + 1] = {1 , 1 , 2 , 0,};

static long long unsigned int countPossibilities(unsigned int n) {
    if (!MAP[n]) {
       MAP[n] = countPossibilities(n-1) + countPossibilities(n-2);
    }
    return MAP[n];
}

int main() {
   printf("%llu",countPossibilities(steps));
}

回答12:

Here is a C++ solution. This prints all possible paths for a given number of stairs.

// Utility function to print a Vector of Vectors
void printVecOfVec(vector< vector<unsigned int> > vecOfVec)
{
    for (unsigned int i = 0; i < vecOfVec.size(); i++)
    {
        for (unsigned int j = 0; j < vecOfVec[i].size(); j++)
        {
            cout << vecOfVec[i][j] << " ";
        }
        cout <<  endl;
    }
    cout << endl;
}

// Given a source vector and a number, it appends the number to each source vectors
// and puts the final values in the destination vector
void appendElementToVector(vector< vector <unsigned int> > src,
                           unsigned int num,
                           vector< vector <unsigned int> > &dest)
{
    for (int i = 0; i < src.size(); i++)
    {
        src[i].push_back(num);
        dest.push_back(src[i]);
    }
}

// Ladder Problem
void ladderDynamic(int number)
{
    vector< vector<unsigned int> > vecNminusTwo = {{}};
    vector< vector<unsigned int> > vecNminusOne = {{1}};
    vector< vector<unsigned int> > vecResult;

    for (int i = 2; i <= number; i++)
    {
        // Empty the result vector to hold fresh set
        vecResult.clear();

        // Append '2' to all N-2 ladder positions
        appendElementToVector(vecNminusTwo, 2, vecResult);

        // Append '1' to all N-1 ladder positions
        appendElementToVector(vecNminusOne, 1, vecResult);

        vecNminusTwo = vecNminusOne;
        vecNminusOne = vecResult;
    }

    printVecOfVec(vecResult);
}

int main()
{
    ladderDynamic(6);
    return 0;
}

回答13:

may be I am wrong.. but it should be :

S(1) =0
S(2) =1

Here We are considering permutations so in that way

S(3) =3
S(4) =7