CODEWITHSUNDEEP
algorithmdynamic-programming
Clay
Clay

Reputation: 2999

Abstract the "stair climbing" algorithm to allow user input of allowed step increment

After looking at the common stair climbing problem, I started to wonder if this could be abstracted to a function that allows for the entry of both number of stairs and the max increment steps allowed as parameters.

I would like to be able to write a function with this signature. If max_step_increment is 4, that means the stair-climber could takes steps of 1, 2, 3, or 4 at a time.

def stair_paths(num_steps, max_step_increment):
    ...
    return answer

I would call this function like stair_paths(10, 4).

Upvotes: 1

Views: 223

Answers (2)

gknicker
gknicker

Reputation: 5569

Solved in Java. This would be more elegant if your method declaration were:

    int stairPaths(int numSteps, int maxStepIncrement)

As you have defined it, here is the dynamic programming solution:

    int stairPaths(int numSteps, int... stepsAllowed)
    {
        if (stepsAllowed.length == 0) {
            return 0;
        }
        Arrays.sort(stepsAllowed);
        if (stepsAllowed[0] < 1) {
            throw new IllegalArgumentException("Invalid step increment " + stepsAllowed[0]);
        }
         int maxStepIncrement = stepsAllowed[stepsAllowed.length - 1];
        int[] priorElements = new int[maxStepIncrement];
        priorElements[maxStepIncrement - 1] = 1;
        priorElements[maxStepIncrement - 2] = 1;
        for (int i = 2; i <= numSteps; i++) {
            int nextElement = 0;
            for (int j = 0; j < stepsAllowed.length; j++) {
                nextElement += priorElements[maxStepIncrement - stepsAllowed[j]];
            }
            for (int k = 1; k < maxStepIncrement; k++) {
                priorElements[k - 1] = priorElements[k];
            }
            priorElements[maxStepIncrement - 1] = nextElement;
        }
        return priorElements[maxStepIncrement - 1];
    }

Upvotes: 1

songlj
songlj

Reputation: 927

Let f[n] means the number of ways to get to n stairs with all allowed steps.

Initially, f[0]=1, the remaining are all 0.

Then, f[i]=sigma(f[i-allowedSteps[j]]), where allowedSteps[j] are all possible allowed steps.

And the final answer should be f[numStairs], which is f[10] in your example.

Upvotes: 0

Related Questions