首页 > 代码库 > 算法之动态规划法
算法之动态规划法
动态规划算法其实就是一种优化的算法，其基本思想就是将待求解的问题分解成若干子问题，先求解子问题（这些解不是独立的），然互从这些子问题中得到原问题的解。其最终得到的结果往往是最优解。和贪心法不同的是，动态规划法不可以将一个整体进行分割。
举个简单的例子：给出7个数，1,2.....7，从中选出不超过3个使得这3个数的和不超过20.求解时我们应该一步一步进行：
1、先给一个数，然后对7个数进行遍历，找到最大的，为7
2、在找两个数，求其最大和，在和步骤一的最大值进行比较，看看谁大就取哪一个为最大值，在循环遍历找到最大值
3、在找三个数，和步骤二是一样的，最终求得最大值。
其实动态规划法也是这样一个步骤，将其抽象整理为：
1、找出最优解的性质，并刻画其结构特征
2、递归的定义最优解的值
3、以自底向上的方式计算出最优解
4、根据计算最优值时得到的信息，构造一个最优解。
在这有一个问题，为什么求两个数的和最大值和第一个数的最大值进行比较，在这还以背包问题为例，在个数n=5，重量W=17时，求重量不超过W的最大价值，表如下：
在这取n=3时其最大价值为前三个物品的和为19；
当n=4时，说明其可以放进去，故第四个物品的价值为v，而剩下背包最大重量为17-8=9，即在重量不超过9的时候前三个物品放到背包的最大价值为取第三个物品的价值10，所以当n=4时其价值为10+v
最后在进行比较：（10+v）和19哪一个价值大，我们可以知道v是第四个物品的价值，故其最后取值应和v的大小有直接关系，当v>=9时，则最大价值为10+v，反之则为19.正好解释下面这个式子：
总结：动态规划法其本质是变量从小到大不断变化，循环，在一次一次的比较过程中找到那个最优解。
算法之动态规划法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。