> "put in enough fuel so it can land" is not a hard problem to solve with earth rockets, it just costs payload.

I am pretty sure that the convex optimization algorithms used by SpaceX's landing systems are a very recent invention (http://larsblackmore.com/publications.htm). As for worrying about fuel, what's the point of a rocket if it cannot take any payload?