algorithm - 抽象 "stair climbing"算法以允许用户输入允许的步长增量

Question

看了共同点之后stair climbing problem ，我开始怀疑这是否可以抽象为一个函数，该函数允许输入楼梯数和允许的最大增量步数作为参数。

我希望能够用这个签名编写一个函数。如果 max_step_increment 是 4，这意味着爬楼梯的人可以一次走 1、2、3 或 4 步。

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

我会将此函数称为 stair_paths(10, 4)。

Answer 1

用 Java 解决。如果您的方法声明是:

    int stairPaths(int numSteps, int maxStepIncrement)

正如你所定义的，这里是动态规划的解决方案:

    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];
    }