赞
踩
局限性:
1 贪心自顶向下求解,动态规划自底向上求解;
2 贪心最优解一定包含上一步的最优解,动态规划最优解不一定包含上一步的最优解;
贪心:每一步的最优解一定包含上一步的最优解,上一步之前的最优解不作保留;
动态规划:全局最优解不一定包含上一步的最优解,因此需要记录上一步的所有解;
3 贪心不能保证全局最优,动态规划(本质是穷举法)能保证全局最优;
4 贪心复杂度较低,动态规划复杂度较高;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。