Javaの計算マックス階段のステップと私は最近、インターンの位置や質問のいずれかの面接を得た階段

Question

をスキップするが、これに類似していた：

入力：nのアクションの数、kのジャックは、彼がステップの 最大数に到達したいアクションのn個の量を持っていますが、k番目の階段を踏むことができません：あなたは 質問

を踏むことができませんでした階段。それぞれの アクションの場合、ジャックは彼の現在のステップに留まるか、または彼が012番目のアクションを実行している間に が実行されていれば、これを続行することができます。 アクションが終了するまで続きます。

出力：最大階段は、彼はそれが（そこインタビュアーに）Hackerrankを経由して試験し、私は残りのタイミング

で8テストケースのうち、わずか3を通過した

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 = (n * (n+1))/2 

は再配置：：

nで二次方程式である

0 = n^2 + n - 2*k 

を：

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

kは方程式の整数解である場合は、k番目のステップに着陸する予定sqrt(1 + 8*k)が奇数の場合にのみ整数解を持つ。だから、

：

• sqrt(1 + 8*k)が奇数である場合は、あなたがk番目のステップに着陸でしょう。だから、最初のアクションにステップを踏み出さないでください。kに1を忘れてしまいます。最大ステップ数は(n * (n+1))/2 - 1です。

  これは、あなたが欠場したい最初のアクションです。なぜなら、1は、あなたが短くすることができる最小のステップ数であるからです。あなたが2番目のアクションを逃した場合、2番目のステップは最大などよりも短くなります。

• そうでない場合は、単に各アクションにi措置を講じて、最大ステップ数は(n * (n+1))/2