动态规划算法

1、主讲：何芸倩基本概念动态规划动态规划：动态规划是运筹学的一个分支，它将多阶段问题转化为一系列的单阶段问题，利用各个阶段之间的关系，逐个求解。一个问题能用动态规划解决，必须具有一下几个性质。最优子结构最优子结构：假设某问题有N个阶段，对于某一个阶段的决策，可以由其之前某一个阶段的决策来获得，就可以说这个问题具有最优子结构性质，否则就没有。无后效性无后效性：对于一个多阶段问题，某一个问题的决策一旦确定，其后面的阶段如何演变，对当前阶段的决策不造成任何影响，即为无后效性。动态规划的一般解题步骤确定状态确定状态：状态就是我们之前所说的阶段，就是我们之前所说的阶段，我们要确定的是对于某一道题目，要分出什

2、么样的阶段，对于每一个阶段，我们所要做的决策是什么。注意，我们要找的状态必须具有最优子结构性质和无后效性。寻找状态转移关系寻找状态转移关系：确定了状态之后，我们需要寻找状态与状态之间存在着什么样的关系，即如何从某一个状态的决策来推出另一个状态的决策，找到关系以后，就可以列出适用于题目的函数，此函数叫做状态转移方程状态转移方程。动态规划的有两种解题策略：递推和记忆化搜索。动态规划的有两种解题策略：递推和记忆化搜索。例题分析给定一个台阶数为N的楼梯，从第一阶开始走，一步可以迈一阶，也可以迈两阶，问从最底层走到最顶层，有多少种走法。分析：首先，对于某一个台阶，有两种可能性上来，一种迈一阶上来的，一种

3、是迈两阶上来的，那么，迈到这一个台阶的方法数就应该是从迈到前一阶的方法数加上迈到前两阶的方法数，将它数学化以后，也就应该是：dpj=dpj-1+dpj-2其中dpj表示的是迈到第j个台阶所需要的方法数，也就是我们上文所说的状态状态，而刚才所推出来的方程，就是上文说说的状态转移方程状态转移方程。例题分析给定一个mn坐标，每一个坐标点上有一个权值，现在要求你从左上角走到右下角，只能往右走或者往下走，每到一个坐标点，就会获得当前坐标点内的权值，从左上角走到右下角，最多能获得多少价值？分析：对于每一个点，有两个来源，要么是从它左边的点而来，要么就是从它上面的点而来，那么，到达某一个点的最大价值有两种可

4、能，一种是到达它左边的点的最大价值加上它的价值，一种是到达它上面的点的最大价值加上它的价值，我们可以列出这样一个式子：dpij=max(dpi-1j, dpij-1)+mapij对于这个问题，“到达每一个点的最大价值”我们称之为状态状态，那么我们列出的方程，称之为状态转移方程状态转移方程。最长不下降子序列问题分析：对于某一个位置的最长不下降子序列dpi，它可能来源于其之前某一个点的最长不下降子序列长度+1，所以我们的就得找出来那一个点。15158 810102 2171720209 912128 811111121342323状态转移方程：dpi=maxdpj|ji且aj=ai+1最长不下降子

5、序列NlogN解法对于每一个最长不下降子序列，它的末尾元素越小，扩展的空间越大。那么用一个数组f，fi表示最长不下降子序列长度为i且最小的元素。这样一来，我们每扫描到一个新的元素，就在f数组中寻找它应有的位置，把它插入进去，然后对长度进行适当的处理，由于我们维护f数组的原则是“最小，那么我们维护的f数组就是有序的，可以进行二分查找，那么对于N个元素，每一个元素进行一次二分查找，总的时间复杂度就是NlogN。最长公共子序列问题描述：给定两个字符串，求两个字符串的额最长公共子串分析：首先，两个串整个的最长公共子序列，可能来源于这两个串某个部分的最长公共子序列，根据这个思路，我们就可以设计出状态：d

6、pij表示的是第一个串的前i位和第二个串的前j位的最长公共子序列，那么考虑一下，如果第一个串第i位和第二个串第j位不相等的话，那dpij一定是dpi-1j和dpij-1中的一个，理由是，如果它们不相等，那它们肯定不能同时加入到公共子序列的尾部。可想而知，如果它们相等，那dpij就也有可能是dpi-1j-1+1了，综上所述，状态转移方程如下：dpij=max(dpi-1j, dpij-1, dpi-1j-1+1(s1i=s2j)0-1背包问题问题描述：有一个背包，它的容量是V，有N种物品，每种物品只有一件，第i件物品占的容量是ci，价值是wi，求将这些物品放入背包中，所能得到的最大的价值。分析：

7、对于每一个物品，我们只有两种选择：放还是不放。首先根据物品划分状态，我们可以这么想：dpi表示的是将前i个物品放进背包中，所能得到的最大价值，但是这个状态是有问题的，问题在于我们没有限制空间，所以我们可以加上空间的计算。所以状态变成了dpij表示将前i个物品放入容量为j的背包中所能获得的最大价值，这样的话，我们将空间也加以限制，j的最大值为V，也就是说我们求出来的策略，放入的物品占用的空间不会超过限制。然后对于状态，dpij取决于第i个物品是放还是不放，如果不放进去，dpij就来源于将前i-1个物品放入了容量为j的空间中，如果放进去了，dpij就来源于将前i-1个物品放进了容量为j-ci的空间

8、中，综上所述，状态转移方程如下：dpij=max(dpi-1j, dpi-1j-ci+wi);0-1背包问题的优化刚刚我们得到的状态转移方程，时间复杂度和空间复杂度都是O(N*V)的，时间复杂度已经非常优了，不必优化，但是空间复杂度是可以优化的。刚刚我们是用的二维数组来记录状态，能否只用一维数组来记录状态呢？我们只用dpj来表示容量为j的背包所能得到的最大价值呢？实际上，这需要我们枚举空间的时候要按照从V到0的顺序来枚举。理由如下：如果我们按照0到V的顺序来枚举的话，对于第i个物品，枚举的空间只要满足了ci，物品就会被放进去，也就是说，当出现ci能放的状态的时候，我们找到的子状态中会有之前放过ci的状态，而如果我们倒叙枚举空间的话，我们得到的子状态是之前没有算过的，也就是说，对于第i个物品，我们得到一个满足ci的子状态的时候，当前的背包中是没有被放过ci的，这样一来，就能保证物品是唯一的了。已枚举正枚举未枚举物品方向空间方向0jj-ci每次的子状态都在已枚举之中已枚举部分中会有ci的存在正向枚举反向枚举已枚举未枚举v0j-cijv物品方向空间方向每次的子状态都在未枚举之中未枚举部分中不会有ci的存在背包问题的扩展背包问题是一类问题，0-1背包是背包问题的基础，而0-1背包的状态转移方程也是所有背包