动态规划初步

[toc]

什么是动态规划

  • 动态规划是一种方法,或者说思想,它并不是某种特定算法。
  • 动态规划方法的通俗解释:将原来比较复杂的问题分解为若干比较简单的子问题,将这些子问题逐个解决,并存储这些子问题的答案,原来的问题的答案将会从这些分解了的子问题的答案中导出。等到下一次遇到了相同的子问题时,我们只是提取出事前存储的问题的答案,而不是重新做一次计算。
  • 对上面通俗解释的解释:无论是原问题,还是子问题,都是问题,我们拿到一个问题,给他分解为若干子问题,那么接下来我们如何解决子问题?那就是把每个子问题当成原问题再度分解,得到子问题的子问题,然后为了解决这些“子问题的子问题”,我们再度分解。。。直到最终我们得到了已经无法再分的“原子问题”,我们假定原子问题是可以很好地被解决的,那么我们理论上只要解决的全部的原子问题,再回推,就可以解决掉全部子问题,最终解决最根本的问题,也就是我们拿到的问题。而动态规划方法体现在我们加速这个过程上,在问题的分解过程中,我们可能会遇到重复的情况,如果我们对这些重复的情况调用之前计算好的答案,就不用再次深入分解问题,这样能大大加快整个求解进程。
  • 动态规划的关键字:递推、记忆化、状态转移

状态

什么是状态

  • 字面含义:物质系统所处的状况。
  • 我们这里所说的状态是一种抽象观念。
  • 在动态规划的设计上,一个“状态”,表达的是在某个情形下的子问题。
  • 在动态规划的操作上,状态最终表现为一个又一个的值,也就是在某个特定情形下的子问题的答案。

状态转移

  • 基于当前状态和其他输入,移动到其他状态。
  • 说人话:某个东西现在是某个样子的,然后我对他动了些手脚,这个东西变成了另外一幅样子。
  • 当前状态能不能转移到当前状态?可以
  • 如何表达状态转移?
    • 状态转移方程(你可以列个公式)
    • 状态转移图(你可以把状态形象化为点,把转移条件形象化为边)
    • 状态转移表(你听说过函数表吗?虽然没怎么用过但这是初中内容。)

那么状态和动态规划有什么关系?

上面说到了,在动态规划里的“状态”表达的是“子问题”,前面也说了,动态规划整体来看是一个操作子问题的方法,这样我们也可以说动态规划是一个操作状态的方法。在动态规划过程中,我们分解当前状态,得到子状态,处理子状态,记忆子状态,最终处理好全部需要处理的状态,从所有状态中挑出合适的、我们需要的状态来代表最终答案。

用动态规划解决问题

必要条件

不是所有的问题都能用动态规划解决,能够使用动态规划方法解决的问题必须满足以下两个基本性质:

  • 对于一个问题,如果它取得了最优解,那么这个问题所能分解出来的所有子问题的解也是最优的,这个性质称为最优子问题/最优子结构
  • 如果我们已经解决了一些问题,那么当我们解决其他问题的时候,已经解决的问题的答案必须不能受新解决的问题影响。也就是说某个状态之后的过程不可以影响之前的状态。这一性质,称为无后效性

分治?

聪明的你发现了,分治法不也是把当前问题分解为小一点的问题直到不能再分,然后解决原子问题回推得到根问题的答案吗?分治和动态规划有什么区别?

适用于用动态规划法求解的问题,分解后的子问题往往不是独立的,在之后的求解过程中会用到之前已经解决的问题的答案。

上面说过了,动态规划过程中每个子问题的答案将会被保存以避免重复计算,这里才是我们高速解决问题的原因。因此我们有下面这种说法:

使用动态规划有意义的条件

  • 子问题之间不是独立的,一个子问题在之后的求解过程中可能会被多次使用到。这个性质称为重叠子问题
  • 需要注意重叠子问题并不是动态规划适用的必要条件,但是如果没有这个性质,使用动态规划并没有意义。

操作步骤

我们使用动态规划方法解决问题时,一般按照以下思维和操作程序:

  • 分析问题:判定其是否能且有意义使用动态规划。
  • 再度分析:找出将问题分解的方法,将分解后的问题合并的方法,确定原子问题的位置(即边界条件)。
  • 定义状态:确定每个状态对应的问题是什么,答案表示什么,携带的情形是什么。
  • 处理状态:递推 and/or 记忆化。
  • 选择答案:从处理好的状态中选择我们需要的合适的状态作出最终答案。

关键点

  • 状态设计
  • 转移方程
  • 初始化
  • 二次优化(本文不讨论)

如果把目光放长远一点

  • 动态规划方法解决了一个问题,但这很可能并不是你要解决的问题的全部。
  • 递推可以叫动态规划吗?我认为可以,你可以看成每个问题只能分解出一个子问题,虽然感觉上有一点奇怪,而且你要注意到递推过程中并没有重叠子问题,即使你管他叫动态规划,那也是没啥意义的动态规划。
  • 开一下脑洞:你用一种动态规划方法分解出来的原子问题需要另外一种动态规划方法解决?你现在动态规划解决的问题其实只是另一个问题的模块?想想就好了,高中生啥都干的出来。

一些经典且简单的模型

关于Fibonacci

广义/系数Fibonacci

首先要说的是,Fibonacci数列中,最有分量的一句话其实是f_i = f_{i-1} + f_{i-2}f_1f_2的值并不重要,所以我们在这里可以推广Fibonacci数列的含义为只要有这样的递推就可以称为(广义)Fibonacci数列。

我们都知道Fibonacci数列,要想快速应付多次查询我们可以事前预处理,要想快速应付一次巨大的查询我们可以使用矩阵快速幂。那么如果我给出下面的问题呢?

Given f_1 = a,f_2 = b,f_i = f_{i-1} + f_{i-2} for every f >= 3,for each query you will get 3 numbers a,b,c,you have to output f_c in condition of given a and b.

这个问题意外的简单,仔细观察我们就发现了,对于给出的这个数列的每一项,a的系数实际上是f_1=1,f_2=0的Fibonacci数列,b的系数实际上是f_1=0,f_2=1的Fibonacci数列,所以接下来怎么操作想必大家都很清楚。

Fibonacci的前缀和?

是的,也是Fibonacci数列。

前两项的作用

前两项事实上决定了整个Fibonacci数列,因此只要知道前两项,就相当于知道了整个Fibonacci数列。

数字三角形

问题

POJ 1163 The Triangle

解法

我们令A[i][j]表示金字塔从上往下数第i行第j个数。

我们令dp[i][j]表示从金字塔从上往下数第i行第j个数。

对于金字塔上每一个点,我们假定已经计算出了从这个点左下方出发走完金字塔的最优解和右下方走完金字塔的最优解,那么从这个点走完金子塔的最优解已经是从左下方或右下方走完这两个可能性中最优的那个,再加上当前这个点的数值,即:

dp[i][j] = best(dp[i+1][j],dp[i+1][j+1]) + A[i][j]

对于最后一行,因为已经是底部,所以dp[i][j] = A[i][j]

最后,我们需要的答案是从塔尖走完整个金字塔的最优解,即dp[1][1]。

问题解决。

背包问题

背包问题九讲

我们只关心这些内容:

  • 01背包
  • 完全背包
  • 多重背包
  • 滚动数组

最长上升子序列

问题

POJ 2533 Longest Ordered Subsequence

解法

令A[i]表示原数列第i位数。

令dp[i]表示检查到原数列第i位(且最后一位就是第i位)时的最长公共子序列长度。

那么对于没有解决的dp[i],我们依次检查所有在第j位之前的数,假设检查到了第j位:

  • 如果A[j] < A[i],那么我们可以选择在j位表示的最长上升子序列后面添附第i位数,这样得到了一种可能的dp[i]=dp[j]+1
  • 否则,我们只能选择放弃之前的结果,这样得到了一种可能的dp[i]=1
  • 我们综合所有可能的dp[i],选出最大的那个,保存

对于第1位,显然只有它自己一个构成了一个上升序列,因此dp[1] = 1。

这样我们完成了状态转移,最终结果就是dp数组中的最大值.

我们只关心O(n^2)的解法(还有一种O(nlogn)的解法)。

Scroll to top