算法:动态规划

算法:动态规划

        经历过很多算法题,其中最常见的解题方法便是动态规划。

        相关概念

        动态规划(dynamic programming,即dp),是一种常见的求解最优解的方案,他通过将复杂的问题拆分为单阶段的小问题求解,核心思想是递推,通过简单基础的解一步步接近最优解。

    寻求最优解

        对于一个算法问题,总有一个相对令人满意的解,但却不一定是我们想要的最优解,譬如在解决动态规划中最经典的背包问题时,有些人首先想到简单省心的贪心算法,取价值最高或是性价比最高的物品组合,这种方案得到的很有可能是最优解,但贪心的算法并不适用于动态规划领域,若是物品中恰好有能将背包塞得很满的组合,而采用贪心策略却浪费了很多背包空间。其实贪心策略本身更多也是一种“相对最优”的解决方案,而很少是真正的最优,这一点请务必斟酌。

    阶数

        通常解一个dp的算法题解是通过一个已知答案的解按表达式推导到最终我们想要的结果,依据题目的复杂程度会有不同的阶数,譬如最简单的爬楼梯解题所求是一个数组,那么它是一个一阶问题,但是背包问题所求是一个二维的表格(涉及到重量、价值两个维度的求解),所以它是二阶问题。问题的阶数将直接影响到推导问题的难度和其执行的时间复杂度。

    无后效性

        动态规划的题目都有这样的一种特性:给出了发展阶段中的某一个状态,状态会受到且只会受到该状态前的多个状态影响,而之后的状态不会影响到此刻。譬如:在爬楼梯问题中,当我们已经求出到n节楼梯的问题答案f(n),后面无论怎样爬楼梯,都不会对f(n)造成影响。无后效性是一个问题能够采用动态规划思路解题的首要前提。

    状态转移方程

        这是动态规划领域中最核心的概念,可以说一个问题能推导出状态转移方程,一个问题就已经求出大半了,这个方程表达了我们要求的状态与之前状态的关系,可以通过它将由我们已知解的状态推导至待求的未知解,例如在爬楼梯问题中,我们假设f(n)为当台阶为n阶时的解,那么有:

        以上便是题目的状态转移方程,通过方程可以很容易的利用递归写出解题的方法。

        动态规划的适用性和解题过程

    适用性和局限性

        不得不提的是,并不是所有类型的问题只要能被拆分成最优子结构就可以利用动态规划解题,通常我们选择动态规划是因为题目具有如下的特征:

    解题思路

        求解动态规划问题的思路一般都是一成不变的:

  1. 分析题目,判断问题的状态,首先确定题目可以拆分最优子结构并且适合使用动态规划解决;

  2. 求出需要的已知解,构造状态转移方程

  3. 通过状态转移方程编写算法

     我们可以采用两种基本的方式接近最优解,一个是自底向上由已知解逐渐填充数组直至待求解,一个是自顶向下利用递归最终到达已知解。

        例题们


2019-07-06鱼鱼

{{blog.title}}

创建于 {{blog.createTimeStr}}   created  by  {{blog.author}} {{tag}}
最后修改于 {{blog.timelineStr}}
修改文档