That's exactly how I approach these problems: I think that's a hard problem so how about just a brute force solution first to validate correctness? Then a few minutes later you realize the repeated subproblem structure and turn brute force into DP.