Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
这题是个经典的动态规划（Dynamic Programming）问题，当前问题的解决依赖于子问题的答案。以前上算法选修课的时候这快内容是必讲的，但是当时对这个问题一知半解，感觉好难啊，就算当时懂了过了一段时间又忘了。然而DP却是算法里面最基本也最常用的技能，必须掌握！于是去网上搜了一些资料，发现好像也没那么难，结合例子很好理解，学完这块内容基本的DP问题就可以解决了。
动态规划-从新手到专家
这篇文章说的详细了，自己在这里只记录下一些要点，以供日后回忆。
1.什么是动态规划
动态规划是一种求解多阶段决策过程的最优解算法，含有[……]