标签归档:Dynamic Programming

Perfect Squares

点击量:239

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.什么是动态规划
动态规划是一种求解多阶段决策过程的最优解算法,含有[……]

继续阅读