Greedy and dynamic programming

Two ways to build an answer out of smaller answers. Greedy takes the best step available and never reconsiders; dynamic programming considers everything but refuses to solve the same thing twice.

Knowing which applies is most of the work, and there is a test for it.

#Greedy, and the question that decides whether it is allowed

Making change for 30 from coins of 25, 10 and 5, always taking the largest that fits: 25, then 5. Two coins, and it is optimal.

Now coins of 25, 10 and 1, making 30. Greedy takes 25, then five 1s — six coins. The right answer is three 10s.

Same algorithm, same shape of problem, and it is wrong on the second. So greedy is not a technique you apply; it is a property a problem either has or does not:

Does taking the locally best step always leave a situation from which the overall best answer is still reachable?

For the first coin set, yes. For the second, no — taking 25 destroys the 10-10-10 answer. Nothing in the code tells you which you have, which is why greedy solutions need an argument, not just a test.

Where greedy provably works, it is the cheapest thing available: interval scheduling by earliest finish time, Huffman coding, Dijkstra's next-cheapest-vertex, Kruskal's cheapest-edge-that-does-not-cycle.

#When greedy fails, the answer is usually "try everything, but remember"

static long fib(int n) { return n < 2 ? n : fib(n-1) + fib(n-2); }

Correct, elegant, and it re-solves the same subproblems an exponential number of times. fib(40) computes fib(38) twice, fib(37) three times, fib(36) five times — the counts are themselves Fibonacci numbers.

### naive fib(40)     = 102334155  (285 ms)
### memoised fib(90)  = 2880067194370816120  (0 ms)

Read those two lines together. The naive version took 285 milliseconds for 40. The memoised version did 90 in unmeasurable time — and 90 is not twice as hard as 40, it is astronomically harder. Naive fib(90) would not finish in your lifetime.

The change is four lines:

static long fib(int n, long[] memo) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib(n-1, memo) + fib(n-2, memo);
}

That is dynamic programming. Not a technique with its own theory — recursion, plus not doing the same work twice.

#The two conditions

A problem is a DP when both hold:

1. Optimal substructure — the best answer is built from best answers to smaller versions. (Greedy needs this too.)
2. Overlapping subproblems — those smaller versions repeat. (Greedy problems do not have this; that is why greedy can throw away what it has seen.)

If only the first holds, it is divide and conquer — merge sort, binary search — and there is nothing to memoise because nothing repeats.

#Top-down or bottom-up

Memoisation is top-down: write the recursion, add a cache. Natural to write from the problem statement, and it only computes states you actually need. Its cost is the call stack — and the recursion lesson's ceiling of about forty-five thousand frames is real here.

Tabulation is bottom-up: fill a table from the smallest case upward.

long[] dp = new long[n+1];
dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];

No recursion, no stack limit, and often less memory — because you can frequently discard everything except the last row or two:

long a = 0, b = 1;
for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }

O(n) time, O(1) space. Recognising that the table only ever reads a fixed window back is the standard second optimisation, and on a large DP it is the difference between fitting in memory and not.

#Recognising a DP

The signals, in rough order of reliability:

• The question asks for a minimum, maximum, or count of ways.
• You can describe the answer for n in terms of the answer for smaller n.
• The obvious recursion is exponential, and you can see the same arguments recurring.
• Choices at each step, where an earlier choice constrains later ones.

The standard shapes worth recognising rather than deriving: coin change, knapsack, longest common subsequence, edit distance, longest increasing subsequence, paths through a grid.