算法设计与分析
动态规划的基本思想是什么？
题目
动态规划的基本思想是什么？
参考答案和解析
正确答案:
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。
贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；
而分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。
不足之处：如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。
贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；
而分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。
不足之处：如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案
第1题：
企业系统规划法的基本思想是什么?
参考答案：信息支持企业运行。通过自上而下地识别系统目标、企业过程和数据，然后对数据进行分析，自下上地设计管理信息系统。该管理信息系统支持企业目标的实现，表达所有管理层次的要求，向企业提供一致性信息，对组织机构的变动具有适应性。
第2题：
寿命表的基本思想是什么？
假定有同时出生的一代人（一般定为10万人），按照某个时期当地人口实际年龄组死亡率而陆续死亡，直到全部死完为止。用寿命表方法计算出一系列统计指标，其中这一代人在不同年龄组的“死亡概率”、“死亡人数”、刚满某年龄时的“尚存人数”及“预期寿命”是主要寿命表指标。
略
第3题：
简述动态规划法的基本思想。
A.不能延伸网络可操作的距离
B.不能过滤网络流量
C.不能在网络上发送变弱的信号
D.不能放大变弱的信号
参考答案：B
第4题：
动态规划算法的基本思想是将待求解问题分解成若干（），先求解（），然后从这些（）的解得到原问题的解。
正确答案:子问题；子问题；子问题
第5题：
运用动态规划的方法解决多阶段决策问题的解题步骤是什么？
正确答案: （1）分阶段，确定阶段变量
（2）定状态，正确选择状态变量，明确其具体含义
（3）取决策，确定决策变量及允许决策集合
（4）列出状态转移方程
（5）确定阶段指标函数及他们之间的关系
第6题：
动态规划的求解的要求是什么（ ）
A.给出最优状态序列
B.给出动态过程
C.给出目标函数值
D.给出最优策略
B.给出动态过程
C.给出目标函数值
D.给出最优策略
答案：A,C,D
解析：
第7题：
微程序控制的基本思想是什么？
微程序控制技术在现今计算机设计中得到广泛的采用，其实质是用程序设计的思想方法来组织操作控制逻辑。
略
第8题：
动态规划最优化原理是什么?
参考答案：一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略。
第9题：
简述动态规划法的基本思想。
正确答案: 为了节约重复求相同子问题的时间，引入一个表（数组），不管它们是否对最终解有用，把新的子问题的解答存于该表中，待以后遇到同样子问题时，就不再重复求该子问题，而直接从表中取出该子问题的解答，这就是动态规划法所采用的基本思想。
第10题：
算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么？
正确答案: 分治策略的基本思想是把一个规模为n的问题划分为若干个规模较小、且与原问题相似的子问题，然后分别求解这些子问题，最后把各子结果合并得到整个问题的解。分解的子问题通常与原问题相似，所以可以递归地使用分治策略来求解。
贪心策略的基本思想是把一个整体最优问题分解为一系列的最优选择问题，决策一旦做出，就不能再更改。它是通过若干次的贪心选择而得出最优解（或较优解）的一种解题策略。
动态规划策略与贪心策略类似，将一个问题划分为重复的子问题，通过对相同子问题的求解来解决较大问题，即将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心策略中，每采用一次贪心准则便做出一个不可撤回的决策，可能得不到问题的最优解。而在动态规划中，处理要按照某种规则进行选择，还要考察每个最优决策序列中是否包含一个最优子序列，目的是得到问题的最优解。
回溯策略也叫试探法，它的基本思想是：在一些问题求解进程中，先选择某一种可能情况向前探索，当发现所选用的试探性操作不是最佳选择，需退回一步，重新选择继续进行试探，直到找到问题的解或者证明问题无解。
分支定界策略也经常被称为分支限界策略，它的基本思想是：首先确定目标值的上下界，然后一边搜索一边剪掉空间树的某些不可能产生最优解的分支，提高搜索效率。