判断题
适中
#24823
如果一个最值问题可以用动态规划在多项式时间内求解,那么也一定存在一种贪心策略,可以在多项式时间 内求得最优解。
如果一个最值问题可以用动态规划在多项式时间内求解,那么也一定存在一种贪心策略,可以在多项式时间 内求得最优解。
答案与解析
正确答案:错
解析
动态规划适用于具有最优子结构和重叠子问题的问题,通过自底向上求解所有子问题保证全局最优。贪心算法基于贪心选择性质,在每一步选择局部最优,期望达到全局最优,其正确性依赖于问题是否满足贪心选择性和最优子结构。两个算法的适用条件不同:动态规划能解决的问题不一定满足贪心选择性质,因此无法保证存在贪心策略得到最优解。判断时需分析两类算法对问题结构性质的要求差异,不能由动态规划可解推出贪心策略必然存在。