In the problems in this card, even though I know dynamic programming can be used to solve them, the solutionssometimes seem too clever. There is often a huge leap between the naive, brute force solution and the dynamic programming solution.

For example, in the maximal square problem, how does someone who has never seen the problem get from the brute force solution of checking every square incrementing width and height by 1 for every top left corner to realizing that you can determine the side length of squares ending in a bottom right corner from the three nearest points up and to the left?

How does this work out in interviews? What happens if one is not clever enough and only finds a brute force solution with a slight optimization?