动态规划算法的研究

2020-10-09石少俭张弘石峥

电脑知识与技术 2020年18期

关键词：算法

石少俭张弘石峥

摘要：算法是计算机程序员必备的一项技术。动态规划算法能解决具有最优子结构和重叠子问题的问题。通过构造合适的递归方程，利用动态规划算法或者备忘录方法解决问题。

关键词：算法;动态规划算法;最优子结构;重叠子问题

中图分类号：0158 文献标识码：A

开放科学（资源服务）标识码（OSID）：

文章编号：1009-3044（2020）18-0048-02

1 引言

算法，晦涩难懂，但又是IT领域最受重视的素养之一。动态规划算法是一种比较抽象的算法。动态规划法最早是在应用数学中被大家认同，由美国的著名数学家贝尔曼在研究应用数学的最优控制问题时提出的。动态规划法有着广泛的应用[1-4]。

2 算法思想

动态规划算法的基本要素：最优子结构性质和子问题重叠性质。

定义1.[5]问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。

定义2.[5]把问题分解成子问题时，如果每次产生的子问题有一些是重复的，这种性质称为子问题的重叠性质。

定义3.[5]为每个解过的子问题建立了备忘录，这种方法称为备忘录方法。

利用动态规划算法解决问题的基本步骤：首先由问题的定义分析问题是否具有最优子结构性质和重叠子问题的特性，如果问题有这两个特性，该问题就可以利用动态规划算法解决;利用最优子结构性质构造出最优值的递推方程;利用动态规划算法或者备忘录方法进行求解。

3 与其他算法的联系与区别

解决实际问题时，经常使用的经典算法除动态规划算法外，还有分治算法和贪心算法，这些算法共同的特性是都具有最优子结构性质。动态规划算法的本质特性是最优子结构性质和子问题的重叠性质。分治算法的本质特性是最优子结构性质和独立子问题。所以判断一个问题是用分治算法还是用动态规划算法解决的根本点是原问题分解成子问题的重叠性。子问题没有重叠的或者很少重叠的问题利用分治算法求解，重叠子问题多的问题利用动态规划算法解决。贪心算法的本质特性是最优子结构性质和贪心选择性质。问题如果具有贪心选择性质，利用贪心算法解决。否则考虑利用分治算法或者动态规划算法解决。

4 应用

例1.最少硬币问题：设有n种不同面值的硬币，各硬币的面值存于数组T[1：n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组C[1：n]中，设计一个用最少硬币找钱m的方法。

解题思路：问题最容易想到的解决方法是利用贪心算法，一个简单例子：T[1，3]=[1，5，11]，m=15，贪心算法的最优解是5个硬币，而问题的最优解为3个硬币，所以最少硬币问题不能用贪心算法解决。

规模为n的最少硬币问题的解一定包含规模小于n的最少硬币问题，所以问题具有最优子结构性质和子问题的重叠性质，利用动态规划算法求解。

数学模型：设xi表示第i个面值硬币所用的数量。

例2.平面直线交点问題：平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。

解题思路：设n条直线的交点数为p（n），考虑它的子问题，p（k），k

递归方程：第n+l条直线与这n条直线相交的情况为：仅与这n条直线中的i条平行。p（n+I）=p（n -ij+（i -I）.（n-i ），i=0，l…k，利用该递推方程，很容易地解决此问题。

例如n=5，P（5）=0，4，6，7，8，9，10。

例3.最大子段和问题：给定由n个整数（包含负整数）组成的序列a1，a2，…，an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。

解题思路：问题满足最优子结构性质，不满足贪心性质，考虑利用分治算法和动态规划算法解决。

分治算法：将所给的序列a[1：n]分为长度相等的两段a[1;n/2]和a[n/2+1：n]，分别求出这两段的最大子段和，再合并成原问题的值。算法复杂性为T（n）= O（nlogn）。