Greedy
Retrieval: greedy or a table?
Two problems rebuilt cold, plus the test that decides which unit a problem belongs to.
Key idea
Can you write the exchange argument?
That is the whole test. If you can show that some optimal solution can be modified to contain your greedy choice without getting worse, the greedy algorithm is correct and you should write the single pass.
If you cannot, assume it is wrong and build the table. A greedy rule with no argument behind it is a guess, and the counterexamples in this unit's first lesson show how ordinary those guesses look.
Tip
Three shapes the argument takes
The choice is forced: no other option is legal, as with the smallest remaining value having to start a run. This is the strongest and needs no exchange at all.
The choice dominates: it leaves you at least as well placed as any alternative, as with finishing earliest freeing the resource soonest.
A block is excluded: rather than justifying what you keep, you prove a whole range of options cannot work and discard them together, as with the reset in the circular-route problem.
Tip
And a note on the two framings
Several problems here can be presented as dynamic programming with the space collapsed. That is not a coincidence and it is not a weakness of either framing.
When both apply, say so. It demonstrates that you know why the greedy version is safe rather than that you remembered it.
Greedy or table?
You must select items with weights and values to maximize value under a weight limit, where each item may be taken at most once. Is a greedy rule by value-per-weight correct?
Jump Game II, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
Edit Distance, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.