Dynamic Programming
Exact technique that stores overlapping subproblems in a table.
Also called: Dynamic Programming · DP · 동적 프로그래밍
An exact technique that breaks a problem into subproblems, solving each once and storing it in a table (memoization) to build the optimum. The 0/1 Knapsack Problem is solved by pseudo-polynomial DP with remaining capacity as the state, and the recursive subdivision of Guillotine Cutting fits DP (the Gilmore-Gomory multistage recursion) too. Because it scales with the numeric values (capacity, dimensions) rather than the item count, large values can make it expensive.
Claims & evidence
Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.
No claims recorded yet.