动态规划算法与分治算法差别

⑴ 【算法】请问动态规划和分治策略的差别是不是就在于对子问题的处理方式上

动态规划与分治策略都是将一个问题分解成为若干子问题，动态规划和分治相比，则有一个非常有用的性质，就是 动态规划中使用的子问题有大部分都是相同的（重叠子问题），这样我就可以通过记录每个子问题的答案使得 每个子问题 不被重复计算，从而 做到了 时间复杂度 上的 本质优化。
但是有些问题本身的子问题就不怎么重复，那样的话其实用不用动态规划都是一样的。

⑵ 动态规划算法的基本思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。

拓展资料：

动态规划的实质是分治思想和解决冗余，因此动态规划是一种将问题实例分析为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略
动态规划所针对的问题有一个显着的特征，即它对应的子问题树中的子问题呈现大量的重复。动态规划的关键在于，对于重复的子问题，只在第一次遇到时求解，并把答案保存起来，让以后再遇到时直接引用，不必要重新求解。

⑶ 算法策略的算法策略间的关系

1、对问题进行分解的算法策略——分治法与动态规划法
共同点：（1）分治法与动态规划法实际上都是递归思想的运用
（2）二者的根本策略都是对问题进行分解，找到大规模与小规模的关系，然后通过解小规模的解，得出大规模的解
不同点： 适用于分治法的问题分解成子问题后，各子问题间无公共子子问题，而动态规划法相反。
动态规划法 = 分治算法思想 + 解决子问题间的冗余情况
2、多阶段逐步解决问题的策略——贪心算法和动态规划法
贪心算法：每一步都根据策略得到一个结果，并传递到下一步，自顶向下，一步一步地做出贪心决策。
动态规划算法：每一步决策得到的不是一个唯一结果，而是一组中间结果（且这些结果在以后各步可能得到多次引用），只是每一步都使问题的规模逐步缩小，最终得到问题的一个结果。

⑷ 动态规划和贪心算法的区别

动态规划和贪心算法的区别

1、动态规划算法中，每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题时才能做出选择。而贪心算法，仅在当前状态下做出最好选择，即局部最优选择，然后再去解做出这个选择后产生的相应的子问题。

2、动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常自顶向下的方式进行。

⑸ 简述贪心，递归，动态规划，及分治算法之间的区别和联系

联系：都是问题求解之时的一种算法。

区别：

一、作用不同

1、贪心算法：把子问题的解局部最优解合成原来解问题的一个解。

2、递归算法：问题解法按递归算法实现。如Hanoi问题；数据的结构形式是按递归定义的。如二叉树、广义表等。

3、动态规划：动态规划算法通常用于求解具有某种最优性质的问题。

4、分治算法：可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。

二、方法不同

1、贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

2、递归算法：通过重复将问题分解为同类的子问题而解决问题。

3、动态规划：将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。

4、分治算法：将一个规模为N的问题分解为K个规模较小的子问题。

三、特点不同

1、贪心算法：根据题意选取一种量度标准。

2、递归算法：递归就是在过程或函数里调用自身。

3、动态规划：虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

4、分治算法：原问题可以分解为多个子问题；原问题在分解过程中，递归地求解子问题；在求解并得到各个子问题的解后。

⑹ 比较“分治法”和“动态规划法”的异同点和优缺点

共同点：
将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。
不同点：
1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；
而分治法中子问题相互独立。
2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；
而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。

⑺ 动态规划算法的分段每一段必须是相同的吗

是的，动态规划算法的分段每一段必须是相同的是的每一段必须是相同的因为动态规则的算法他是这样设置的我们在每一个分段它的一个数值呢必须是相同所以他的每一段的动态规则赋值呢是一样的所以他每一段必须是相同的这是他规划算法的是的每一段必须是相同的

⑻ 动态规划

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解 决策过程最优化 的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了着名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显着的效果。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如 线性规划、非线性规划 )，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定， 它依赖于当前面临的状态，又影响以后的发展 。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个 前后关联具有链状结构的多阶段过程 就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的， 决策依赖于当前状态，又随即引起状态的转移 ，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。 动态规划算法与分治法类似 ，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是， 适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的 。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

以一个例子来说明动态规划的概念(leetcode第5题最长回文子串)：

在这个例子中，一个字符串如果是回文子串，那么去掉头尾也照样是回文子串。而每一个字符都有可能是最长回文子串的一部分。

上面这个例子使用一个二维数组表示各个阶段的状态，这个二维数组的行是子串的起始位置，列是子串的结束位置。由于j>=i，所以只需要考虑二维数组的主对角线的上半部分，对角线上的值永远是true。用true表示这个子串是回文串，false不是回文串。那么对于某个固定位置的数组元素来说，它的值依赖于左下角的元素的值。进行填充的时候只能一列一列地进行填充，同一列的元素从上到下依次填充。

⑼ 递归，分治算法，动态规划和贪心选择的区别

递归，简单的重复，计算量大。 分治，解决问题独立，分开计算，如其名。 动态规划算法通常以自底向上的方式解各子问题， 贪心算法则通常以自顶向下的方式进行； 动态规划能求出问题的最优解，贪心不能保证求出问题的最优解