There's a well-known dynamic programming problem that goes by the name of the "gold mine." You have a n x n grid, each cell of which contains a certain value of coins. You begin at the bottom left and can only move right, up, or diagonally up and right. The goal of your algorithm is to determine the path through the mine that maximizes the amount of gold you collect.
An example solution: http://www.ideserve.co.in/learn/gold-mine-problem
Is it possible to solve this problem using a divide-and-conquer approach using O(n) space or less, while still using O(n^2) time?
My first suspicion is that you can divide up the grid into quadrants recursively, find the best path in each of those quadrants, then somehow merge the result in the end to get the best path through the whole thing. Using only O(n) space you can store the paths in each quadrant, since the longest path through each of them is 2n - 2. But in doing that you "forget" about other cells that are worth points that weren't chosen, and the answer provided by that algorithm has the tendency to be incorrect. If we look through all the cells at each merge step in an attempt to remember the discarded ones (which takes n^2 time), then the solution to the recurrence relation for running time becomes n^2 log n instead of n^2, via the master theorem. The merge step has to be done in O(n log n) or O(n).
The space requirement here is the kicker more so than the time requirement.