动态规划-NOIP提高组历年高频考点(1)

    通过分析NOIP2011-2018年提高组的试题我们就会发现，考察最多的考点前三名就是模拟，动态规划和贪心算法。简单统计这八年的提高组48个试题我们发现，模拟和动态规划各考察了有11次之多，模拟我们不过多提及，今天我们说说常见且考察最多的动态规划算法。

1.      概论：

        动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。动态规划不是一种具体的算法，而是对解最优化问题的一种途径、一种方法。常见的动态规划有线性动态规划、区域动态规划、树型动态规划、背包问题等。

        

2.      知识点梳理：

2.1 基本模型

    动态规划是解决一个多阶段决策过程的最优化问题的常用算法。所谓多阶段决策过程，指的是这样一类特殊过程，过程可以按照一定的顺序分解成若干个相互联系的阶段，在每一个阶段都需要作出决策。全部过程的决策是一个决策序列。而动态规划，就是解决这类过程的最优化问题。利用动态规划解决的多阶段决策过程，必须要有最优子结构特点。即对于一个最优的决策序列，其子序列也是最优的。

2.2  基本思想

    动态规划算法的基本思想是：将带求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解中得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，避免重复求解。该思想与记忆化搜索类似，即将计算步骤中的过程保存下来，避免重复运算。

2.3  基本步骤

    动态规划算法求解的基本步骤如下：

（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

（2）确定状态和状态变量：注意状态必须满足无后效性。

（3）确定决策：找到子问题是进行动态规划的重要一步。动态规划和递推更多应考虑本问题由哪些已解决子问题构成，而不是考虑本问题对将来哪些问题有贡献。

（4）确定边界条件，写出状态转移方程。

（5）代码编程

2.4  常见动态规划类型

• 线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等

• 区域动规：石子合并，加分二叉树，统计单词个数等

• 树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等

• 背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题等

2.5  动态规划的优化

    在NOIP中，动态规划很少需要优化。唯一较为常见的优化方式为“状态压缩”。由于动态规划实质上是一种以时间换空间的解题方式，因此，在空间复杂度上要非常注意。“状态压缩”根据题意找到一个更好的存储状态，避免朴素算法的空间复杂度过大。最经典的例子是NOIP2005中的题目“过河”。

之前在清北学堂信息学训练营的一些入门资料分享给大家：

 总结一下动态规划一些需要了解的思想，出自大牛博主“英雄哪里出来 ”

1、递推

递推作为动态规划的基本方法，对理解动态规划起着至关重要的作用。

我们来看下面一个例题：

骨牌铺方格递推

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 744 Accepted Submission(s): 478

Problem Description 在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数. 例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：

Input 输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。

Output             对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。

Sample Input 1 3 2

Sample Output 1 3 2

        这是一个经典的递推问题，如果觉得无从下手，我们可以来看一个更加简单的问题，把问题中的“3”变成“2”（即在一个2XN的长方形方格中铺满1X2的骨牌的方案）。这样问题就简单很多了，我们用f[i]表示2Xi的方格铺满骨牌的方案数，那么考虑第i列，要么竖着放置一个骨牌；要么连同i-1列，横着放置两个骨牌，如图2所示。由于骨牌的长度为1X2，所以在第i列放置的骨牌无法影响到第i-2列。很显然，图一 -1-2中两块黑色的部分分别表示f[i-1]和f[i-2]，所以可以得到递推式f[i] = f[i-1] + f[i-2] (i >= 2)，并且边界条件f[0] = f[1] = 1。

图一 -1-2

再回头来看3 X N的情况，首先可以明确当N等于奇数的时候，方案数一定为0。所以如果用f[i] (i 为偶数) 表示3Xi的方格铺满骨牌的方案数，f[i]的方案数不可能由f[i-1]递推而来。那么我们猜想f[i]和f[i-2]一定是有关系的，如图一 -1-3所示，我们把第i列和第i-1列用1X2的骨牌填满后，轻易转化成了f[i-2]的问题，那是不是代表f[i] = 3*f[i-2]呢？

图一 -1-3

仔细想想才发现不对，原因是我们少考虑了图一 -1-4的情况，这些情况用图一 -1-3的情况无法表示，再填充完黑色区域后，发现和f[i-4]也有关系，但是还是漏掉了一些情况。

图一 -1-4

上面的问题说明我们在设计状态（状态在动态规划中是个很重要的概念，在本章的第4小节会进行介绍总结）的时候的思维定式，当一维的状态已经无法满足我们的需求时，我们可以试着增加一维，用二维来表示状态，用f[i][j]表示(3 X i) + j个多余块的摆放方案数，如图一 -1-5所示：

图一 -1-5

转化成二维后，我们可以轻易写出三种情况的递推式，具体推导方法见图一 -1-6。

f[i][0] = f[i-2][0] + f[i-1][1] + f[i-2][2]

f[i][1] = f[i-1][2]

f[i][2] = f[i][0] + f[i-1][1]

边界条件     f[0][0] = f[1][1] = f[0][2] = 1

图一 -1-6

如果N不是很大的情况，到这一步，我们的问题已经完美解决了，其实并不需要求它的通项公式。

如果需要通项公式，那么假设dp[i]为铺满2*n网格的方案数.那么dp[i]=dp[i-1]+dp[i-2]。其中dp[i-1]为铺满2*(n-1)网格的方案数(既然前面的2*(n-1)的网格一已经铺满,那么最后一个只能是竖着放)。dp[i-2]为铺满2*(n-2)网格的方案数(如果前面的2*(n-2)的网格已经铺满,那么最后的只能是横着放,否则会重复).其实这种递推题，在独立思考得到递推公式后,其实可以将输入样例带进去验证一下.需要注意的是dp[50]已经到200多亿了，这时候需要用long long 。

2、记忆化搜索

      递推说白了就是在知道前i-1项的值的前提下，计算第i项的值，而记忆化搜索则是另外一种思路。它是直接计算第i项，需要用到第 j 项的值( j < i)时去查表，如果表里已经有第 j 项的话，则直接取出来用，否则递归计算第 j 项，并且在计算完毕后把值记录在表中。记忆化搜索在求解多维的情况下比递推更加方便，【例题3】是我遇到的第一个记忆化搜索的问题，记忆犹新。

      【例题3】这个问题直接给出了一段求函数w(a, b, c)的伪代码：

      function w(a, b, c):

       if a <=0 or b <=0 or c <=0, then returns:1

       if a >20or b >20or c >20, then returns: w(20,20,20)

       if a < b and b < c, then returns: w(a, b, c-1)+ w(a, b-1, c-1)- w(a, b-1, c)    

       otherwise it returns: w(a-1, b, c)+ w(a-1, b-1, c)+ w(a-1, b, c-1)

      要求给定a, b, c，求w(a, b, c)的值。

      乍看下只要将伪代码翻译成实际代码，然后直接对于给定的a, b, c，调用函数w(a, b, c)就能得到值了。但是只要稍加分析就能看出这个函数的时间复杂度是指数级的（尽管这个三元组的最大元素只有20，这是个陷阱）。对于任意一个三元组(a, b, c)，w(a, b, c)可能被计算多次，而对于固定的(a, b, c)，w(a, b, c)其实是个固定的值，没必要多次计算，所以只要将计算过的值保存在f[a][b][c]中，整个计算就只有一次了，总的时间复杂度就是O(n^3)，这个问题的n只有20。

3、状态和状态转移         

      在介绍递推和记忆化搜索的时候，都会涉及到一个词---状态，它表示了解决某一问题的中间结果，这是一个比较抽象的概念，例如【例题1】中的f[i][j]，【例题2】中的FA[i]、FB[i]，【例题3】中的f[a][b][c]，无论是递推还是记忆化搜索，首先要设计出合适的状态，然后通过状态的特征建立状态转移方程（f[i] = f[i-1] + f[i-2] 就是一个简单的状态转移方程）。

4、最优化原理和最优子结构

      在介如果问题的最优解包含的子问题的解也是最优的，就称该问题具有最有子结构，即满足最优化原理。这里我尽力减少理论化的概念，而改用一个简单的例题来加深对这句话的理解。

     【例题4】给定一个长度为n(1 <= n <= 1000)的整数序列a[i]，求它的一个子序列(子序列即在原序列任意位置删除0或多个元素后的序列)，满足如下条件：

      1、该序列单调递增；

      2、在所有满足条件1的序列中长度是最长的；

      这个问题是经典的动态规划问题，被称为最长单调子序列。

      我们假设现在没有任何动态规划的基础，那么看到这个问题首先想到的是什么？

      我想到的是万金油算法---枚举（DFS），即枚举a[i]这个元素取或不取，所有取的元素组成一个合法的子序列，枚举的时候需要满足单调递增这个限制，那么对于一个n个元素的序列，最坏时间复杂度自然就是O(2n)，n等于30就已经很变态了更别说是1000。但是方向是对的，动态规划求解之前先试想一下搜索的正确性，这里搜索的正确性是很显然的，因为已经枚举了所有情况，总有一种情况是我们要求的解。我们尝试将搜索的算法进行一些改进，假设第i个数取的情况下已经搜索出的最大长度记录在数组d中，即用d[i]表示当前搜索到的以a[i]结尾的最长单调子序列的长度，那么如果下次搜索得到的序列长度小于等于d[i]，就不必往下搜索了（因为即便继续往后枚举，能够得到的解必定不会比之前更长）；反之，则需要更新d[i]的值。如图一-4-1，红色路径表示第一次搜索得到的一个最长子序列1、2、3、5，蓝色路径表示第二次搜索，当枚举第3个元素取的情况时，发现以第3个数结尾的最长长度d[3] = 3，比本次枚举的长度要大（本次枚举的长度为2），所以放弃往下枚举，大大减少了搜索的状态空间。

图一-4-1

      这时候，我们其实已经不经意间设计好了状态，就是上文中提到的那个d[i]数组，它表示的是以a[i]结尾的最长单调子序列的长度，那么对于任意的i，d[i] 一定等于 d[j] + 1 ( j < i )，而且还得满足 a[j] < a[i]。因为这里的d[i]表示的是最长长度，所以d[i]的表达式可以更加明确，即：

      d[i] = max{ d[j] | j < i && a[j] < a[i] } + 1

      这个表达式很好的阐释了最优化原理，其中d[j]作为d[i]的子问题，d[i]最长（优）当且仅当d[j]最长（优）。当然，这个方程就是这个问题的状态转移方程。状态总数量O(n), 每次转移需要用到前i项的结果，平摊下来也是O(n)的,所以该问题的时间复杂度是O(n^2)，然而它并不是求解这类问题的最优解，下文会提到最长单调子序列的O(nlogn)的优化算法。

5、决策和无后效性

      一个状态演变到另一个状态，往往是通过“决策”来进行的。有了“决策”，就会有状态转移。而

无后效性，就是一旦某个状态确定后，它之前的状态无法对它之后的状态产生“效应”（影响）。

      【例题5】老王想在未来的n年内每年都持有电脑，m(y, z)表示第y年到第z年的电脑维护费用，其中y的范围为[1, n]，z的范围为[y, n]，c表示买一台新的电脑的固定费用。给定矩阵m，固定费用c，求在未来n年都有电脑的最少花费。

考虑第 i 年是否要换电脑，换和不换是不一样的决策，那么我们定义一个二元组(a, b)，其中 a < b，它表示了第a年和第b年都要换电脑（第a年和第b年之间不再换电脑），如果假设我们到第a年为止换电脑的最优方案已经确定，那么第a年以前如何换电脑的一些列步骤变得不再重要，因为它并不会影响第b年的情况，这就是无后效性。

更加具体得，令d[i]表示在第i年买了一台电脑的最小花费(由于这台电脑能用多久不确定，所以第i年的维护费用暂时不计在这里面)，如果上一次更换电脑的时间在第j年，那么第j年更换电脑到第i年之前的总开销就是c + m(j, i-1)，于是有状态转移方程：     

d[i] = min{ d[j] + m(j, i-1) |  1 <=  j < i  }

 + c

这里的d[i]并不是最后问题的解，因为它漏算了第i年到第n年的维护费用，所以最后问题的答案：

ans  = min{ d[i] + m(i, n)  | 1 <= i < n }

我们发现两个方程看起来很类似，其实是可以合并的，我们可以假设第n+1年必须换电脑，并且第n+1年换电脑的费用为0，那么整个阶段的状态转移方程就是：

d[i] = min{ d[j] + m(j, i-1) | 1 <= j < i } + w(i)    其中w(i) = (i==n+1)?0:c;

d[n+1]就是我们需要求的最小费用了。

本文动态规划思想部分内容由博主“英雄哪里出来 ”整理，原文地址：http://www./menjitianya/archive/2015/10/23/212084.html，希望本文能对你有所帮助！