1 / 5 Dynamic Programming: States & Transitions

Remember the Past

Which problem characteristic indicates that dynamic programming might be applicable? (Select all that apply)

A

Overlapping subproblems (same subproblems are solved multiple times)

B

Subproblems are independent

C

Greedy choice property (local optimum leads to global optimum)

D

The problem involves finding any valid solution

E

Optimal substructure (optimal solution contains optimal solutions to subproblems)