동적 계획법은 큰 문제를 작은 문제의 답으로 표현할 수 있을 때 사용합니다. 한 번 계산한 하위 문제 결과를 메모나 표에 저장하고 다시 필요할 때 읽습니다.
피보나치 수열처럼 같은 가지가 반복되는 경우 재귀 호출 수가 크게 줄어듭니다. 상태 정의와 계산 순서를 잘못 잡으면 필요한 하위 문제가 빠지거나 메모리만 늘어납니다.
언제 쓰나
최적 경로, 문자열 비교, 경우의 수처럼 하위 문제가 반복될 때 씁니다.
동적 계획법
Dynamic programming
겹치는 하위 문제의 답을 저장해 재계산을 줄입니다.
···
<div class="v"><header><b>MEMO TABLE</b><span id="state"></span></header><main><div class="cells" id="cells"></div><div class="formula" id="formula"></div></main><footer>each answer computed once</footer></div>.v{width:min(92vw,660px);height:min(86vh,310px);box-sizing:border-box;padding:clamp(9px,2.5vmin,18px);border:1px solid var(--line);border-radius:14px;background:var(--surface);display:flex;flex-direction:column;gap:7px;color:var(--fg);font:500 clamp(15px,4.5vmin,19px)/1.25 var(--font-sans, sans-serif)}.v header,.v footer{display:flex;justify-content:space-between;align-items:center;gap:8px;white-space:nowrap}.v header b{color:var(--accent);font-size:.9em}.v header span,.v footer{color:var(--muted);font-size:.82em}.v main{flex:1;min-height:0;position:relative;overflow:hidden}.v .mono{font-family:ui-monospace,SFMono-Regular,Consolas,monospace}.v .active{background:var(--accent)!important;color:var(--bg)!important;border-color:var(--accent)!important}.v .muted{opacity:.45} .cells{height:57%;display:flex;align-items:center;justify-content:center;gap:4px}.cell{width:32px;height:38px;border:1px solid var(--line);border-radius:5px;display:grid;place-items:center;font:700 .9em ui-monospace,monospace}.formula{text-align:center;color:var(--accent);font:600 .9em ui-monospace,monospace}const f=[0,1,1,2,3,5];let n=2;function draw(){document.getElementById("cells").innerHTML=f.map((x,i)=>"<div class=\"cell "+(i===n?"active":i>n?"muted":"")+"\">"+(i<=n?x:"?")+"</div>").join("");document.getElementById("formula").textContent="F("+n+") = F("+(n-1)+") + F("+(n-2)+")";document.getElementById("state").textContent="cache hit: "+(n-1)+","+(n-2);n=n===5?2:n+1}draw();setInterval(draw,980)