1.4买书问题之贪心算法和动态规划

　　对于自己的白痴程度，自己已经快无法忍受了，到现在还不明白贪心算法和动态规划。　

1.贪心算法

　　在对问题求解时，总是做出当前看来最好的选择，也就是说它不从整体最优上加以考虑，而是仅在局部考虑最优解。

　　虽然，它不能为所有问题提供最优解答，但是对广泛问题能产生整体最优解或近似解。

　基本思路：

　　1.建立数序模型

　　2.把问题分解若干子问题，依次求解

　　3.把局部最优解合成原问题的一个解

2.动态规划

　　通过百度一下，从百度知道得到了一个很好的解答！

　　动态规划的基本思想就是把全局问题化为局部问题，为了全局优化必须局部优化。

　　能用动态规划解决的问题，肯定可以通过搜索解决。可是搜索的方法时间复杂度太高，怎样优化呢？我们一般采用的方法叫做记忆优化搜索，就是搜完某个解之后把它保存起来，下一次搜索到这个地方的时候，调用上一次的搜索结果。这样就解决了重复状态的问题。记忆化搜索就是动态规划的一种实现方法。那么那些状态必须可以转给i状态，于是你就确定了状态转移方程，然后你需要确定边界条件，将边界条件赋予初值，此时就可以从前往后枚举状态进行状态转移了。

　　光说不干，等于白看！！在网上搜一下好的题做一下。

本文 由 cococo点点 创作，采用 知识共享 署名-非商业性使用-相同方式共享 3.0 中国大陆 许可协议进行许可。欢迎转载，请注明出处：
转载自：cococo点点 http://www.cnblogs.com/coder2012