Java计算楼梯的最大步数并跳过楼梯

Question

我最近接受了实习职位的面试，其中一个问题与此类似:

Input: n for number of actions, k for a stair that you could not step on

Question: Jack has n amount of actions where he wants to reach the maximum number of steps but cannot step on the kth stair. For each action, Jack can either stay at his current step or jump i steps if he is on his ith action and this keeps going until he finished his nth action.

Output: The maximum stair he can reach within n actions

它是通过 Hackerrank 测试的(面试官在那里)，我只通过了 8 个测试用例中的 3 个，其余的都超时了

这是我即时编码的解决方案，我无法优化它，想知道是否有更优化的解决方案:

static int maxStep(int n, int k) {
    int result = 0;
    if (n == 0) {
        return result;
    } 
    return maxStepHelper(n,0, k, result);
}

static int maxStepHelper(int n,int i,int k,int result) {
    // At n+1 steps, previous steps' results are recorded and this is mainly used to stop and show previous results
    if (i == n+1) {
        return result;
    }
    int nextStep = i + result;
    if (nextStep == k) {
       return maxStepHelper(n,i+1,k,result);
    } 
    return Math.max(maxStepHelper(n,i+1,k,result),maxStepHelper(n,i+1,k,result+i));
}

请注意，我使用了可能没有帮助的递归方法

Answer 1

这里不需要递归或动态规划；这只是一点数学。

如果您在每个回合中走 i 步，您将走 (n * (n+1))/2 步。如果 k 是方程的整数解，您将进入第 k 步:

k = (n * (n+1)) / 2

重新排列:

0 = n^2 + n - 2*k

n 中的二次方程:

n = (-1 +/- sqrt(1 + 4*1*2*k)) / 2

只有当 sqrt(1 + 8*k) 是奇数时才有整数解。

所以:

• 如果 sqrt(1 + 8*k) 是奇数，您将进入第 k 步。所以，只要不在第一个 Action 上迈出一步，你就会错过 k 1。最大步数是 (n * (n+1))/2 - 1。

  这是您不想错过的第一个 Action ，因为 1 是您可以缩短的最少步数。如果你错过了第二个 Action ，你将比最大值少 2 步等。

• 否则，每个 Action 只走i步，最大步数为(n * (n+1))/2