動的プログラミングのメモ帳

Question

このdpの例では、どのようにメモ処理が機能しているか教えてください。 dp example problem, codechef

iが貼り付け部は、入力が4の場合と同様であり、最適なステップが4/2になり、または入力のため= 10がなぜ計算するときに理由コードが N-1、すなわち4-1計算されたn-1すべての助けをいただければ幸いです。 ダイナミックプログラミングには新しいので、私にご負担ください。ダイナミックプログラミングで

Answer 1

メモ化は、単に下位問題に対する解決策を記憶しています。入力n = 4の場合、その解を計算します。したがって、ステップ1を試してください。1 +サブ問題n = 3の解を引きます。これを評価するには、問題をn = 3で解く必要があります。なぜなら、これまで解けなかったからです。したがって、0を出力するn = 1の基本問題になるまでもう一度試してください。

現在の問題に対して手順1を試した後、手順2を実行してnを分けてから手順3を試してみます。すべてのサブ問題に対してすべての手順を試しますが、すべてのサブ問題に最高の価値を保存するので、再度発生したときにこれを使用できます。

たとえば、ステップ1を試した後にn = 4に戻ったときにステップ2を実行すると、n/2を使用することができ、n = 2の最適値缶合計2

Answer 2

にので、出力1 + 1であり、N = 2の最適値は、リンクがかなり明確に説明します。​​が1にnを変換するためのステップの最小数である場合には、任意のn > 1のために、我々は、以下の再発関係があります：あなたのケースのために

F(n) = 1 + min(F(n-1), F(n/2), F(n/3)) // if n divisible by 2 and 3 
F(n) = 1 + min(F(n-1), F(n/2))   // if n divisible by 2 and not 3 
F(n) = 1 + min(F(n-1),   F(n/3)) // if n divisible by 3 and not 2 
F(n) = 1 +  F(n-1)     // all other cases 

、n=4を、私たちは、ある1を決定するF(n-1)とF(n/2)を計算する必要があります最小。

n=10の場合は、最初にF(9)と評価します。この評価の間に、すべての値F(8), F(7), ... F(2)が計算され、がメモされたとなります。次に、F(10/2) = F(5)を評価すると、単にの値がという配列の値を調べることになります。これは多くの計算を節約します。

Answer 3

JSで次のようにすることができます。

function getSteps(n){ 
 
    var fs = [i => i%3 ? false : i/3, i => i%2 ? false : i/2, i => i-1], 
 
    res = [n], 
 
    chk; 
 
    while (res[res.length-1] > 1) { 
 
    chk = false; 
 
    fs.forEach(f => !chk && (chk = f(res[res.length-1])) && res.push(chk)); 
 
    } 
 
    return res; 
 
} 
 
var result = getSteps(1453); 
 
console.log(result); 
 
console.log("The number of steps:",result.length);