CMP.3:4.1 - State what a subcomputation means

Describe the result of one subcomputation as a function of its inputs and fixed environment. Include every condition that can change the returned answer or its use. A pair of sequence indices identifies an edit-distance subproblem only within specified sequences, edit operations and costs.

For optimization, distinguish the best remaining value from accumulated cost already incurred. If two histories lead to the same remaining problem but have different past costs, share the remaining answer and combine it with each history’s cost. Merging the complete histories may lose a better total. When history changes the allowed future choices, retain that history information in the state.

This question is also useful before an implementation exists: identify the small family of questions that many possible constructions would ask. A recursion tree can then be designed around those questions instead of optimized after the fact.