COMPSCI320 Chap.8 Dynamic Programming Foundations
Dynamic Programming Foundations
Dynamic programming stores the answers to overlapping subproblems so each is solved once.
This chapter follows the tutorial recipe of state definition, transition and base cases, fills and traces back a table for the maximum-weight independent set on a path, builds a transition over all earlier states for the longest rising subsequence, and solves weighted interval scheduling with a predecessor index.
Each worked problem states the meaning of a table entry before its equation, fills the table and traces back the decisions.
The practice cards cover a one-dimensional run and weighted interval scheduling, and the closing note connects the circular version of the path problem from the fourth programming assignment.
What this chapter covers
- 01
State, transition and base cases
- 02
Memoised recursion and bottom-up tables
- 03
Independent sets on a path
- 04
Longest rising subsequence
- 05
Maximum subarray and sub-matrix sums
- 06
Weighted interval scheduling
Worked example · free
Find a maximum-weight independent set on a path
- 1Start with S[0] = 0 and S[1] = 5.
- 1Fill S[2] to S[6] as 8, 11, 11, 18, 18.
- 1Trace back: S[5] = S[3] + 7, S[3] = S[1] + 6, and S[1] takes vertex 1.
- 1The set of vertices 1, 3 and 5 has weight 5 + 6 + 7 = 18.
Key terms
- Dynamic Programming
- A technique that solves a problem through a table of overlapping subproblems, each solved once.
- State Definition
- A precise statement of what one table entry represents in a dynamic program.
- Memoisation
- Caching the result of each recursive call so that a repeated subproblem is answered from the cache.
- Independent Set
- A set of vertices in which no two are joined by an edge.
- Transition Equation
- The formula that expresses one table entry of a dynamic program through smaller entries.
- Traceback
- The backward walk through a filled table that recovers the decisions behind an optimal value.
Dynamic Programming Foundations FAQ
What should come first in a dynamic programming answer?
The state definition, written in words. Say exactly what one entry means, for example the best weight using the first i vertices, and check that the original problem is one of the entries. The transition, base cases and running time all follow from that sentence, and a wrong or vague state is the most common reason a recurrence fails.
How do I get the running time of a dynamic program?
Multiply the number of table entries by the work needed to fill one entry. The path problem has n entries and constant work each, so linear time. The longest rising subsequence has n entries but each scans all earlier days, so quadratic time. Add the cost of any sorting or preprocessing, such as computing predecessor indices.
Is memoisation or a bottom-up loop better?
They do the same work when every subproblem is needed. Memoisation follows the recurrence directly and computes only the entries actually reached; a bottom-up loop avoids recursion overhead and depth limits on very long inputs. For a by-hand exam answer either is fine, provided you state the order in which entries are filled.
How do I recover the actual solution, not just its value?
Store the table, then walk backwards from the answer entry, asking which option of the transition produced each value. For the path problem, an entry equal to the previous one means the current vertex was skipped; otherwise it was taken and the walk jumps back two places. Recording the choice in a second array makes this automatic.
Exam move
For every problem in this chapter write the three recipe parts on one card: the state in words, the transition with every option, and the base cases. Solve each card on a fresh instance, then trace back the decisions. Finally state each running time as entries times work per entry.
Before the exam, solve one new problem from scratch with the recipe, timing yourself, and check the answer against a brute-force enumeration on a tiny input. Keep a list of transitions you have seen, noting whether each looks back one step, two steps or over all earlier states.
Working through Dynamic Programming Foundations in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Dynamic Programming Foundations question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
