的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