Lessons from Perfect Squares

Three points:

$1.$ Sequences define the structure of choices in DP problems. Here, the sequence of perfect squares determines which transitions are valid.

$2.$ Algebraic manipulation (solving $k^2 \leq i$ for $k$) gives you loop bounds. This prevents checking invalid values.

$3.$ Time complexity analysis uses summation formulas. The $\sum_{i=1}^{n} \sqrt{i}$ term approximates to $O(n \sqrt{n})$.