n steps with 1, 2 or 3 steps taken. How many ways

问题:

If we have n steps and we can go up 1 or 2 steps at a time, there is a Fibonacci relation between the number of steps and the ways to climb them. IF and ONLY if we do not count 2+1 and 1+2 as different.

However, this no longer the case, as well as having to add we add a third option, taking 3 steps. How do I do this?

What I have:

1 step = 1 way
2 steps = 2 ways: 1+1, 2
3 steps = 4 ways: 1+1+1, 2+1, 1+2, 3

I have no idea where to go from here to find out the number of ways for n stairs

I get 7 for n = 4 and 14 for n= 5 i get 14+7+4+2+1 by doing the sum of all the combinations before it. so ways for n steps = n-1 ways + n-2 ways + .... 1 ways assuming i kept all the values. DYNAMIC programming. 1 2 and 3 steps would be the base-case is that correct?

回答1:

I would say that the formula will look in the following way:

K(1) = 1
K(2) = 2
k(3) = 4
K(n) = K(n-3) + K(n-2) + K(n - 1)

The formula says that in order to reach the n'th step we have to firstly reach:

• n-3'th step and then take 3 steps at once i.e. K(n-3)
• or n-2'th step and then take 2 steps at once i.e. K(n-2)
• or n-1'th step and then take 1 steps at once i.e. K(n-1)

K(4) = 7, K(5) = 13 etc.

You can either utilize the recursive formula or use dynamic programming.

回答2:

Python solutions:

Recursive O(n)

This is based on the answer by Michael.

def recursive(n):
    if n < 4:
        initial = [1, 2, 4]
        return initial[n-1]
    else:
        return recursive(n-1) + recursive(n-2) + recursive(n-3)

Recursive O(log(n))

This is per a comment for this answer. This tribonacci-by-doubling solution is analogous to the fibonacci-by-doubling solution in the algorithms by Nayuki. Note that multiplication has a higher complexity than constant.

def recursive_doubling(n):
    def recursive_tribonacci_tuple(n):
        """Return the n, n+1, and n+2 tribonacci numbers for n>=0.

        Tribonacci forward doubling identities:
        T(2n)   = T(n+1)^2 + T(n)*(2*T(n+2) - 2*T(n+1) - T(n))
        T(2n+1) = T(n)^2 + T(n+1)*(2*T(n+2) - T(n+1))
        T(2n+2) = T(n+2)^2 + T(n+1)*(2*T(n) + T(n+1))
        """
        assert n >= 0
        if n == 0:
            return 0, 0, 1  # T(0), T(1), T(2)

        a, b, c = recursive_tribonacci_tuple(n // 2)
        x = b*b + a*(2*(c - b) - a)
        y = a*a + b*(2*c - b)
        z = c*c + b*(2*a + b)

        return (x, y, z) if n % 2 == 0 else (y, z, x+y+z)
    return recursive_tribonacci_tuple(n)[2]  # Is offset by 2 for the steps problem.

Iterative O(n)

This is motivated by the answer by 太極者無極而生. It is a modified tribonacci extension of the iterative fibonacci solution. It is modified from tribonacci in that it returns c, not a.

def iterative(n):
    a, b, c = 0, 0, 1
    for _ in range(n):
        a, b, c = b, c, a+b+c
    return c

Iterative O(log(n)) (left to right)

This is per a comment for this answer. This modified iterative tribonacci-by-doubling solution is derived from the corresponding recursive solution. For some background, see here and here. It is modified from tribonacci in that it returns c, not a. Note that multiplication has a higher complexity than constant.

The bits of n are iterated from left to right, i.e. MSB to LSB.

def iterative_doubling_l2r(n):
    """Return the n+2 tribonacci number for n>=0.

    Tribonacci forward doubling identities:
    T(2n)   = T(n+1)^2 + T(n)*(2*T(n+2) - 2*T(n+1) - T(n))
    T(2n+1) = T(n)^2 + T(n+1)*(2*T(n+2) - T(n+1))
    T(2n+2) = T(n+2)^2 + T(n+1)*(2*T(n) + T(n+1))
    """
    assert n >= 0
    a, b, c = 0, 0, 1  # T(0), T(1), T(2)
    for i in range(n.bit_length() - 1, -1, -1):  # Left (MSB) to right (LSB).
        x = b*b + a*(2*(c - b) - a)
        y = a*a + b*(2*c - b)
        z = c*c + b*(2*a + b)
        bit = (n >> i) & 1
        a, b, c = (y, z, x+y+z) if bit else (x, y, z)
    return c

Notes:

• list(range(m - 1, -1, -1)) == list(reversed(range(m)))
• If the bit is odd (1), the sequence is advanced by one iteration. This intuitively makes sense after understanding the same for the efficient integer exponentiation problem.

Iterative O(log(n)) (right to left)

This is per a comment for this answer. The bits of n are iterated from right to left, i.e. LSB to MSB. This approach is probably not prescriptive.

def iterative_doubling_r2l(n):
    """Return the n+2 tribonacci number for n>=0.

    Tribonacci forward doubling identities:
    T(2n)   = T(n+1)^2 + T(n)*(2*T(n+2) - 2*T(n+1) - T(n))
    T(2n+1) = T(n)^2 + T(n+1)*(2*T(n+2) - T(n+1))
    T(2n+2) = T(n+2)^2 + T(n+1)*(2*T(n) + T(n+1))

    Given Tribonacci tuples (T(n), T(n+1), T(n+2)) and (T(k), T(k+1), T(k+2)),
    we can "add" them together to get (T(n+k), T(n+k+1), T(n+k+2)).

    Tribonacci addition formulas:
    T(n+k)   = T(n)*(T(k+2) - T(k+1) - T(k)) + T(n+1)*(T(k+1) - T(k)) + T(n+2)*T(k)
    T(n+k+1) = T(n)*T(k) + T(n+1)*(T(k+2) - T(k+1)) + T(n+2)*T(k+1)
    T(n+k+2) = T(n)*T(k+1) + T(n+1)*(T(k) + T(k+1)) + T(n+2)*T(k+2)
    When n == k, these are equivalent to the doubling formulas.
    """
    assert n >= 0
    a, b, c = 0, 0, 1  # T(0), T(1), T(2)
    d, e, f = 0, 1, 1  # T(1), T(2), T(3)
    for i in range(n.bit_length()):  # Right (LSB) to left (MSB).
        bit = (n >> i) & 1
        if bit:
            # a, b, c += d, e, f
            x = a*(f - e - d) + b*(e - d) + c*d
            y = a*d + b*(f - e) + c*e
            z = a*e + b*(d + e) + c*f
            a, b, c = x, y, z
        # d, e, f += d, e, f
        x = e*e + d*(2*(f - e) - d)
        y = d*d + e*(2*f - e)
        z = f*f + e*(2*d + e)
        d, e, f = x, y, z
    return c

Approximations

Approximations are of course useful mainly for very large n. The exponentiation operation is used. Note that exponentiation has a higher complexity than constant.

def approx1(n):
    a_pos = (19 + 3*(33**.5))**(1./3)
    a_neg = (19 - 3*(33**.5))**(1./3)
    b = (586 + 102*(33**.5))**(1./3)
    return round(3*b * ((1./3) * (a_pos+a_neg+1))**(n+1) / (b**2 - 2*b + 4))

The approximation above was tested to be correct till n = 53, after which it differed. It's certainly possible that using higher precision floating point arithmetic will lead to a better approximation in practice.

def approx2(n):
    return round((0.618363 * 1.8392**n + \
                  (0.029252 + 0.014515j) * (-0.41964 - 0.60629j)**n + \
                  (0.029252 - 0.014515j) * (-0.41964 - 0.60629j)**n).real)

The approximation above was tested to be correct till n = 11, after which it differed.

回答3:

This is my solution in Ruby:

# recursion requirement: it returns the number of way up
# a staircase of n steps, given that the number of steps
# can be 1, 2, 3

def how_many_ways(n)
  # this is a bit Zen like, if 0 steps, then there is 1 way
  # and we don't even need to specify f(1), because f(1) = summing them up
  # and so f(1) = f(0) = 1
  # Similarly, f(2) is summing them up = f(1) + f(0) = 1 + 1 = 2
  # and so we have all base cases covered
  return 1 if n == 0

  how_many_ways_total = 0
  (1..3).each do |n_steps|
    if n >= n_steps
      how_many_ways_total += how_many_ways(n - n_steps)
    end
  end
  return how_many_ways_total
end

0.upto(20) {|n| puts "how_many_ways(#{n}) => #{how_many_ways(n)}"}

and a shorter version:

def how_many_ways(n)
  # this is a bit Zen like, if 0 steps, then there is 1 way
  # if n is negative, there is no way and therefore returns 0
  return 1 if n == 0
  return 0 if n < 0
  return how_many_ways(n - 1) + how_many_ways(n - 2) + how_many_ways(n - 3)
end

0.upto(20) {|n| puts "how_many_ways(#{n}) => #{how_many_ways(n)}"}

and once you know it is similar to fibonacci series, you wouldn't use recursion, but use an iterative method:

# 
# from 0 to 27: recursive: 4.72 second
#               iterative: 0.03 second
#

def how_many_ways(n)
  arr = [0, 0, 1]
  n.times do
    new_sum = arr.inject(:+)    # sum them up
    arr.push(new_sum).shift()
  end
  return arr[-1]
end

0.upto(27) {|n| puts "how_many_ways(#{n}) => #{how_many_ways(n)}"}

output:

how_many_ways(0) => 1
how_many_ways(1) => 1
how_many_ways(2) => 2
how_many_ways(3) => 4
how_many_ways(4) => 7
how_many_ways(5) => 13
how_many_ways(6) => 24
how_many_ways(7) => 44
how_many_ways(8) => 81
how_many_ways(9) => 149
how_many_ways(10) => 274
how_many_ways(11) => 504
how_many_ways(12) => 927
how_many_ways(13) => 1705
  .
  .
how_many_ways(22) => 410744
how_many_ways(23) => 755476
how_many_ways(24) => 1389537
how_many_ways(25) => 2555757
how_many_ways(26) => 4700770
how_many_ways(27) => 8646064

I like the explanation of @MichałKomorowski and the comment of @rici. Thought I think if it depends on knowing K(3) = 4, then it involves counting manually.

回答4:

Easily get the intuition for the problem:

Think you are climbing stairs and the possible steps you can take are 1 & 2

The total no. of ways to reach step 4 = Total no. of ways to reach step 3 + Total no of ways to reach step 2

How?

Basically, there are only two possible steps from where you can reach step 4.

1. Either you are in step 3 and take one step
2. Or you are in step 2 and take two step leap

These two are the only possibilities by which you can ever reach step 4

Similarly, there are only two possible ways to reach step 2

1. Either you are in step 1 and take one step
2. Or you are in step 0 and take two step leap

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

F(0) = 0 and F(1) = 1 are the base cases. From here you can start building F(2), F(3) and so on. This is similar to Fibonacci series.

If the number of possible steps is increased, say [1,2,3], now for every step you have one more option i.e., you can directly leap from three steps prior to it

Hence the formula would become

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

See this video for understanding Staircase Problem Fibonacci Series

Easy understanding of code: geeksforgeeks staircase problem

回答5:

Count ways to reach the n^th stair using step 1, 2, 3.

We can count using simple Recursive Methods.

// Header File
#include<stdio.h>
// Function prototype for recursive Approch
int findStep(int);
int main(){
    int n;
    int ways=0;
    ways = findStep(4);
    printf("%d\n", ways);
return 0;
}
// Function Definition
int findStep(int n){
    int t1, t2, t3;
    if(n==1 || n==0){
        return 1;
    }else if(n==2){
        return 2;
    }
    else{
        t3 = findStep(n-3);
        t2 = findStep(n-2);
        t1 = findStep(n-1);
        return t1+t2+t3;
    }
}

回答6:

def count(steps):
  sol = []
  sol.append(1)
  sol.append(1 + sol[0])
  sol.append(1 + sol[1] + sol[0])


  if(steps > 3):
    for x in range(4, steps+1):
        sol[(x-1)%3] = sum(sol)


return sol[(steps-1)%3]

回答7:

My solution is in java. I decided to solve this bottom up.

I start off with having an empty array of current paths [] Each step i will add a all possible step sizes {1,2,3}

First step [] --> [[1],[2],[3]]
Second step [[1],[2],[3]] --> [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1][3,2],[3,3]]

Iteration 0: []
Iteration 1: [ [1], [2] , [3]]
Iteration 2: [ [1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]]
Iteration 3 [ [1,1,1], [1,1,2], [1,1,3] ....]

The sequence lengths are as follows 1 2 3 5 8 13 21

My step function is called build

public class App {



public static boolean isClimedTooHigh(List<Integer> path, int maxSteps){
    int sum = 0;
    for (Integer i : path){
        sum+=i;
    }
    return sum>=maxSteps;
}

public static void modify(Integer x){
    x++;
    return;
}

///  1    2   3

/// 11 12 13
/// 21 22 23
/// 31 32 33

///111 121
public static boolean build(List<List<Integer>> paths, List<Integer> steps, int maxSteps){
    List<List<Integer>> next = new ArrayList<List<Integer>>();
    for (List<Integer> path : paths){
        if (isClimedTooHigh(path, maxSteps)){
            next.add(path);
        }
        for (Integer step : steps){
            List<Integer> p = new ArrayList<Integer>(path);
            p.add(step);
            next.add(p);
        }
    }
    paths.clear();
    boolean completed = true;
    for (List<Integer> n : next){
        if (completed && !isClimedTooHigh(n, maxSteps))
            completed = false;
        paths.add(n);
    }

    return completed;
}

public static boolean isPathEqualToMax(List<Integer> path, int maxSteps){
    int sum = 0;
    for (Integer i : path){
        sum+=i;
    }
    return sum==maxSteps;
}

public static void calculate( int stepSize, int maxSteps ){
    List<List<Integer>> paths = new ArrayList<List<Integer>>();
    List<Integer> steps = new ArrayList<Integer>();
    for (int i =1; i < stepSize; i++){
        List<Integer> s = new ArrayList<Integer>(1);
        s.add(i);
        steps.add(i);
        paths.add(s);
    }
    while (!build(paths,steps,maxSteps));
    List<List<Integer>> finalPaths = new ArrayList<List<Integer>>();
    for (List<Integer> p : paths){
        if (isPathEqualToMax(p, maxSteps)){
            finalPaths.add(p);
        }
    }

    System.out.println(finalPaths.size());
}
public static void main(String[] args){
    calculate(3,1);
    calculate(3,2);
    calculate(3,3);
    calculate(3,4);
    calculate(3,5);
    calculate(3,6);
    calculate(3,7);

    return;
}

}

回答8:

Count total number of ways to cover the distance with 1, 2 and 3 steps.

Recursion solution time complexity is exponential i.e. O(3n).

Since same sub problems are solved again, this problem has overlapping sub problems property. So min square sum problem has both properties of a dynamic programming problem.

public class MaxStepsCount {

     /** Dynamic Programming. */
     private static int getMaxWaysDP(int distance) {

           int[] count = new int[distance+1];
           count[0] = 1;
           count[1] = 1;
           count[2] = 2;

           /** Memorize the Sub-problem in bottom up manner*/
           for (int i=3; i<=distance; i++) {
                count[i] = count[i-1] + count[i-2] + count[i-3];               
           }
           return count[distance];
     }


     /** Recursion Approach. */
     private static int getMaxWaysRecur(int distance) {
           if(distance<0) {
                return 0;
           } else if(distance==0) {
                return 1;
           }
           return getMaxWaysRecur(distance-1)+getMaxWaysRecur(distance-2)
                     +getMaxWaysRecur(distance-3);
     }

     public static void main(String[] args) {
           // Steps pf 1, 2 and 3.
           int distance = 10;

           /** Recursion Approach. */
           int ways = getMaxWaysRecur(distance);
           System.out.println(ways);

           /** Dynamic Programming. */
           ways = getMaxWaysDP(distance);
           System.out.println(ways);
     }
}

My blog post on this:

http://javaexplorer03.blogspot.in/2016/10/count-number-of-ways-to-cover-distance.html

回答9:

Recursive memoization based C++ solution: You ask a stair how many ways we can go to top? If its not the topmost stair, its going to ask all its neighbors and sum it up and return you the result. If its the topmost stair its going to say 1.

vector<int> getAllStairsFromHere(vector<int>& numSteps,  int& numStairs, int currentStair)
{
    vector<int> res;

    for(auto it : numSteps)
        if(it + currentStair <= numStairs)
            res.push_back(it + currentStair);

    return res;
}


int numWaysToClimbUtil(vector<int>& numSteps, int& numStairs, int currentStair, map<int,int>& memT)
{
    auto it = memT.find(currentStair);
    if(it != memT.end())
        return it->second;

    if(currentStair >= numStairs)
        return 1;

    int numWaysToClimb = 0;
    auto choices = getAllStairsFromHere(numSteps,  numStairs, currentStair);
    for(auto it : choices)
        numWaysToClimb += numWaysToClimbUtil(numSteps, numStairs, it, memT);


    memT.insert(make_pair(currentStair, numWaysToClimb));
    return memT[currentStair];
}


int numWaysToClimb(vector<int>numSteps, int numStairs)
{
    map<int,int> memT;
    int currentStair = 0;
    return numWaysToClimbUtil(numSteps, numStairs, currentStair, memT);
}

回答10:

Here is an O(Nk) Java implementation using dynamic programming:

public class Sample {
    public static void main(String[] args) {
        System.out.println(combos(new int[]{4,3,2,1}, 100));
    }

    public static int combos(int[] steps, int stairs) {
        int[][] table = new int[stairs+1][steps.length];
        for (int i = 0; i < steps.length; i++) {

            for (int n = 1; n <= stairs; n++ ) {
                int count = 0;
                if (n % steps[i] == 0){
                    if (i == 0)
                        count++;
                    else {
                        if (n <= steps[i])
                            count++;
                    }
                }

                if (i > 0 && n > steps[i]) {
                    count += table[n - steps[i]][i];
                }

                if (i > 0)
                    count += table[n][i-1];

                table[n][i] = count;
            }
        }

        for (int n = 1; n < stairs; n++) {
            System.out.print(n + "\t");
            for (int i = 0; i < steps.length; i++) {
                System.out.print(table[n][i] + "\t");
            }
            System.out.println();
        }
        return table[stairs][steps.length-1];
    }
}

The idea is to fill the following table 1 column at a time from left to right:

N    (4)    (4,3)  (4,3,2) (4,3,2,1)
1   0   0   0   1   
2   0   0   1   2   
3   0   1   1   3   
4   1   1   2   5   
5   0   0   1   6   
6   0   1   3   9   
7   0   1   2   11  
8   1   1   4   15  
9   0   1   3   18  
10  0   1   5   23  
11  0   1   4   27  
12  1   2   7   34  
13  0   1   5   39  
..
..
99  0   9   217 7803
100             8037

回答11:

Below is the several ways to use 1 , 2 and 3 steps

1: 1
2: 11   2
3: 111 12 21 3
4: 1111 121 211 112 22 13 31
5: 11111 1112 1121 1211 2111 122 212 221 113 131 311 23 32
6: 111111 11112 11121 11211 12111 21111 1113 1131 1311 3111 123 132 312 321 213 231 33 222 1122 1221 2211 1212 2121 2112

So according to above combination the soln should be:

K(n) = K(n-3) + K(n-2) + K(n - 1)
k(6) = 24 which is k(5)+k(4)+k(3) = 13+7+4

回答12:

Java recursive implementation based on Michał's answer:

public class Tribonacci {
    // k(0) = 1
    // k(1) = 1
    // k(2) = 2
    // k(3) = 4
    // ...
    // k(n) = k(n-3) + k(n-2) + k(n - 1)

    static int get(int n) {
        if (n == 0) {
            return 1;
        } if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        //} else if (n == 3) {
        //    return 4;
        } else {
            return get(n - 3) + get(n - 2) + get(n - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println("Tribonacci sequence");
        System.out.println(Tribonacci.get(1));
        System.out.println(Tribonacci.get(2));
        System.out.println(Tribonacci.get(3));
        System.out.println(Tribonacci.get(4));
        System.out.println(Tribonacci.get(5));
        System.out.println(Tribonacci.get(6));
    }
}

回答13:

Maybe its just 2^(n-1) with n being the number of steps?

It makes sence for me because with 4 steps you have 8 possibilities:

4,
3+1,
1+3,
2+2,
2+1+1,
1+2+1,
1+1+2,
1+1+1+1,

I guess this is the pattern