上一篇博客我们讲了分治法,紧接着讲动态规划法:动态规划法和分治法类似,它也是将大问题分解成子问题求解,求最优解,不同的是,如果分解的子问题有很多是相同的,采用分治法相同的子问题会求解多次,很影响效率;动态规划法呢,它会保存已解决的子问题的答案,再有相同的子问题直接用保存的答案就行了,节省了很多计算时间。
如一张图表示:
例:
解:我们先求F(5)的解,如下,以二叉树的结构表示
通过二叉树,我们注意到,F(n)是通过计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的,所以,可以设计一张表填入n+1个F(n)的值。通过下面的表会发现:后一个数等于前面两个数的和。(这就是著名的斐波那契数)
所以,使用动态规划法的情况,对于一个问题具有的性质可以总结为:最优子结构,重叠子问题
适用情况:
(1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
(2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
(3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)
应用实例:
<span style="font-size:14px;"> public class CoinsChange { /** * 硬币找零:动态规划算法 * * @param values * :保存每一种硬币的币值的数组 * @param valueKinds * :币值不同的硬币种类数量,即coinValue[]数组的大小 * @param money * :需要找零的面值 * @param coinsUsed * :保存面值为i的纸币找零所需的最小硬币数 */ public static void makeChange(int[] values, int valueKinds, int money, int[] coinsUsed) { coinsUsed[0] = 0; // 对每一分钱都找零,即保存子问题的解以备用,即填表 for (int cents = 1; cents <= money; cents++) { // 当用最小币值的硬币找零时,所需硬币数量最多 int minCoins = cents; // 遍历每一种面值的硬币,看是否可作为找零的其中之一 for (int kind = 0; kind < valueKinds; kind++) { // 若当前面值的硬币小于当前的cents则分解问题并查表 if (values[kind] <= cents) { int temp = coinsUsed[cents - values[kind]] + 1; if (temp < minCoins) { minCoins = temp; } } } // 保存最小硬币数 coinsUsed[cents] = minCoins; System.out.println("面值为 " + (cents) + " 的最小硬币数 : " + coinsUsed[cents]); } } public static void main(String[] args) { // 硬币面值预先已经按降序排列 int[] coinValue = new int[] { 25, 21, 10, 5, 1 }; // 需要找零的面值 int money = 63; // 保存每一个面值找零所需的最小硬币数,0号单元舍弃不用,所以要多加1 int[] coinsUsed = new int[money + 1]; makeChange(coinValue, coinValue.length, money, coinsUsed); } } </span>
时间: 2024-12-10 03:36:39