的Java计算最大步，然后跳到楼梯

Question

我最近得到了一个实习位置，其中一个问题的采访是与此类似：

输入：N为一个动作数，k楼梯，你可以不踩 上

问题：杰克有他想要达到的步骤 最大数量的措施N量，但在第k个楼梯不可能一步到位。对于每一个 行动，杰克可以保持在他目前的步骤或者如果他的第i个动作 并且这一直持续直到他完成他的第n个 行动，我可以跳下我的步骤。

输出：最大楼梯他可以

据经由Hackerrank测试（与访问者那里），我只通过3超过了8试验例其余超时

n项操作内到达

这是我的解决方案，是在运行编码，我不能对其进行优化，并想知道是否有一个更优化的解决方案：

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个步骤。所以，不要在第一个动作上采取措施，并且您会错过k。最大步数是(n * (n+1))/2 - 1。

  这是你不想错过，因为1是你可以通过短的步骤数最少的第一个动作。如果你错过了第二个动作，你会比最大值等2步

• 否则，只需要在每个操作步骤i和步骤的最大数量为(n * (n+1))/2