常用算法之动态规划法

ゞ浴缸里的玫瑰 2022-08-13 12:54 221阅读 0赞

上一篇博客我们讲了分治法，紧接着讲动态规划法：动态规划法和分治法类似，它也是将大问题分解成子问题求解，**求最优解**，不同的是，如果分解的子问题有很多是相同的，采用分治法相同的子问题会求解多次，很影响效率；动态规划法呢，它会**保存已解决的子问题的答案**，再有相同的子问题直接用保存的答案就行了，节省了很多计算时间。

如一张图表示：

![Center][]

**例：**

![Center 1][]

解：我们先求F(5)的解，如下，以二叉树的结构表示

通过二叉树，我们注意到，F(n)是通过计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。通过下面的表会发现：后一个数等于前面两个数的和。（这就是著名的斐波那契数）

![Center 2][]

**所以，使用动态规划法的情况，对于一个问题具有的性质可以总结为：最优子结构，重叠子问题**

适用情况：

**   **(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>

[Center]: /images/20220810/58bc37d0be834739a43bcac230ae5cd4.png
[Center 1]: /images/20220810/2495d1d8eb6a45a1a7a616223c1ed572.png
[Center 2]: /images/20220810/6557f3ef17e54d35ba6808b0d238615c.png