动态规划总结之：动态规划学习笔记（1）

Posted on | In | | Visitors
学习动态规划过程中的一点思考，关于：1. 动态规划的定义和意义；2. 递推，贪心，搜索，动态规划之间的区别；3. 状态和状态转移方程；4. 最优子结构和无后效性；5. 一些例题。

动态规划是什么？

动态规划是对于 某一类问题 的解决方法，重点在于如何鉴定某一类问题是动态规划可以解决的。

计算机的本质是一个状态机，内存里存储的所有数据构成了当前的状态，CPU只能利用当前的状态计算出下一个状态（不要纠结硬盘之类的外部存储，就算考虑他们也只是扩大了状态的存储容量而已，并不能改变下一个状态只能从当前状态计算出来这一条铁律）当你企图使用计算机解决一个问题是，其实就是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据）以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少，所谓时间复杂度就是从初始状态到达最终状态中间需要多少步！

递推，贪心，搜索，动态规划

问题有线性的和非线形的，比如求斐波那契数列第n项就是一个线形的问题，不需要考虑是不是需要更多的状态，也不需要选择哪些旧状态来计算新状态。对于这样的解法，我们叫递推。

想象另外一个非线形问题的情景，假如把你放在一个围棋棋盘上的某一点，你每一步只能走一格，因为你可以东南西北随便走，所以你当你同样走四步可能会处于很多个不同的位置。从头开始走了几步就是第几个阶段，走了n步可能处于的位置称为一个状态，走了这n步所有可能到达的位置的集合就是这个阶段下所有可能的状态。

假如问题有n个阶段，每个阶段都有多个状态，不同阶段的状态数不必相同，一个阶段的一个状态可以得到下个阶段的所有状态中的几个。那我们要计算出最终阶段的状态数自然要经历之前每个阶段的某些状态。

很多情况下我们并不需要计算出所有状态，因为”下一步的最优是从当前最优得到的“。所以为了计算最终的最优值，只需要存储每一步的最优值即可，解决符合这种性质的问题的算法就叫贪心。

既然问题都是可以划分成阶段和状态的。这样一来我们一下子解决了一大类问题：一个阶段的最优可以由前一个阶段的最优得到。

最麻烦的情况是你需要之前所有的阶段才能得到下一个阶段的最优（比如迷宫最短路径问题）。每个阶段的状态或许不多，但是每个状态都可以转移到下一阶段的多个状态，所以解的复杂度就是指数的，因此时间复杂度也是指数的。解决符合这种性质的问题的算法就叫搜索。

有一类问题，看似需要之前所有的状态，其实不用。不妨也是拿最长上升子序列的例子来说明为什么他不必需要暴力搜索，进而引出动态规划的思路。

寻找最长上升子序列的第i个阶段就是去思考是否要选择第i个数，第i个阶段有两个状态，分别是选和不选。每次当我决定要选择当前数字的时候，只需要和之前选定的一个数字比较就行了！这是和之前迷宫问题的本质不同！我们不用记录之前的所有状态，也不会受到之前的状态组合的影响，我们只需要记录截止到之前的数字的LIS长度。因此第i个阶段的最优解只是由前i-1个阶段的最优解得到的，然后就得到了DP方程。LIS(i) = max{LIS(j)+1} j<i && a[j] < a[i]

所以一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的！

  • 每个阶段只有一个状态->递推；
  • 每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
  • 每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
  • 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

状态和状态转移方程

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
如何拆分问题，是动态规划的核心。而拆分问题，靠的就是状态的定义和状态转移方程的定义。

我的理解：状态就是中间态，就是该问题的子问题的解。将问题重新定义之后找到的一个general state。这个状态，F，可以推出最后的结果，也包含前面所有子问题。

而状态定义好之后，状态和状态之间的关系式，就叫做状态转移方程。

最优子结构，无后效性

每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到

这个性质叫做最优子结构。

而不管之前这个状态是如何得到的（不用记录之前的所有状态，之前的选择不会影响到后面的状态）

这个性质叫无后效性

在迷宫最短路径例子中，之前的路线会影响到下一步的选择

这个令人不开心的情况就叫做有后效性。

符合无后效性的状态定义，我们可以说它具有“最优子结构”的性质，在动态规划中我们要做的，就是找到这种“最优子结构”。在对状态和状态转移方程的定义过程中，满足“最优子结构”是一个隐含的条件（否则根本定义不出来）。
需要注意的是，一个问题可能有多种不同的状态定义和状态转移方程定义，存在一个有后效性的定义，不代表该问题不适用动态规划。动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义，在找到之后，这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义，才是动态规划的本质。

其实动态规划中的最优状态的说法容易产生误导，以为只需要计算最优状态就好，LIS问题确实如此，转移时只用到了每个阶段“选”的状态。但实际上有的问题往往需要对每个阶段的所有状态都算出一个最优值，然后根据这些最优值再来找最优状态。比如背包问题就需要对前i个包（阶段）容量为j时（状态）计算出最大价值。然后在最后一个阶段中的所有状态种找到最优值。

用例子来分析动态规划问题

入门问题

Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that they sum up to S. (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候)

d(i)表示凑够i元需要的最少硬币数量，我们将它定义为该问题的”状态”。A smaller state than state i would be the solution for any sum j, where j<i. For finding a state i, we need to first find all smaller states j (j<i).
For each coin j, Vj 表示硬币的面值，Vj < i, 寻找 the minimum number of coins found for the i-Vj sum(we have already found it previously)，设这个数量为m 如果 m + 1 less than the minimum number of coins already found for current sum i,，那么rewrite the new value。

DP 方程：d(i) = min{d(i-Vj) + 1} (i-Vj >= 0)

Pseudocode:

1
2
3
4
5
6
7
8
9
Set Min[i] equal to Infinity for all of i
Min[0] = 0
For i from 1 to S
For j from 0 to N-1
	if(Vj <= i && Min[i-Vj] + 1 < Min[i])
		Min[i] = Min[i-Vj]+1
Output Min[i]

初级问题

Longest Increasing Subsequence

我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度，其中i<N， 那么上面的问题变成了原问题的一个子问题(问题规模变小了，你可以让i=1,2,3等来分析) 然后我们定义d(i)，表示前i个数中以A[i]结尾的最长非降子序列的长度。OK， 对照“入门”中的简单题，你应该可以估计到这个d(i)就是我们要找的状态。 如果我们把d(1)到d(N)都计算出来，那么最终我们要找的答案就是这里面最大的那个。 状态找到了，下一步找出状态转移方程。

d(i) = Max{d(j)+1} j<i && A[j]<=A[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
public int lis(int[] A, int n){
	int[] temp = new int[n];
	int len = 1;
	for(int i = 0; i < n; i++){
		temp[i] = 1;
		for(int j = 0; j < i; j++){
			if(A[i] >= A[j] && temp[i] < temp[j]+1){
				temp[i] = temp[j]+1;
			}
		if(temp[i] > len) len = temp[i];
	}
	return len;
}

中级问题

二维DP

平面上有N*M个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始， 每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来， 这样下去，你最多能收集到多少个苹果。

解这个问题与解其它的DP问题几乎没有什么两样。第一步找到问题的“状态”， 第二步找到“状态转移方程”，然后基本上问题就解决了。

到达一个格子的方式最多只有两种：从左边来的(除了第一列)和从上边来的(除了第一行)。 因此为了求出到达当前格子后最多能收集到多少个苹果， 我们就要先去考察那些能到达当前这个格子的格子，到达它们最多能收集到多少个苹果。(是不是有点绕，但这句话的本质其实是DP的关键：欲求问题的解，先要去求子问题的解)。

状态S[i][j]表示我们走到(i, j)这个格子时，最多能收集到多少个苹果。那么， 状态转移方程如下：

S[i][j]=A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0)

其中i代表行，j代表列，下标均从0开始；A[i][j]代表格子(i, j)处的苹果数量。

S[i][j]有两种计算方式：1.对于每一行，从左向右计算，然后从上到下逐行处理；2. 对于每一列，从上到下计算，然后从左向右逐列处理。 这样做的目的是为了在计算S[i][j]时，S[i-1][j]和S[i][j-1]都已经计算出来了。

伪代码如下：

1
2
3
4
For i from 0 to N-1
	For j from 0 to M-1
		S[i][j] = A[i][j] + Max(S[i][j-1], if j>0; S[i-1][j], if i>0; 0)
return S[N-1][M-1]

中高级问题

带有额外条件的DP问题。

无向图G有N个结点，它的边上带有正的权重值。

你从结点1开始走，并且一开始的时候你身上带有M元钱。如果你经过结点i，那么你就要花掉S[i]元(可以把这想象为收过路费)。如果你没有足够的钱，就不能从那个结点经过。在这样的限制条件下，找到从结点1到结点N的最短路径。或者输出该路径不存在。如果存在多条最短路径，那么输出花钱数量最少的那条。 限制：1<N<=100 ; 0<=M<=100 ; 对于每个i，0<=S[i]<=100；

如果没有额外的限制条件(在结点处要收费，费用不足还不给过)，那么， 这个问题就和经典的迪杰斯特拉问题一样了(找到两结点间的最短路径)。
在经典的迪杰斯特拉问题中， 我们使用一个一维数组来保存从开始结点到每个结点的最短路径的长度，即M[i]表示从开始结点到结点i的最短路径的长度。

然而在这个问题中，我们还要保存我们身上剩余多少钱这个信息。因此，很自然的，我们将一维数组扩展为二维数组。M[i][j]表示从开始结点到结点i的最短路径长度， 且剩余j元。

在每一步中，对于已经找到的最短路径，我们找到它所能到达的下一个未标记状态(i,j)， 将它标记为已访问(之后不再访问这个结点)，并且在能到达这个结点的各个最短路径中，找到加上当前边权重值后最小值对应的路径，即为该结点的最短路径。

不断重复上面的步骤， 直到所有的结点都访问到为止(这里的访问并不是要求我们要经过它， 比如有个结点收费很高，你没有足够的钱去经过它，但你已经访问过它) 最后Min[N-1][j]中的最小值即是问题的答案(如果有多个最小值，即有多条最短路径，那么选择j最大的那条路径，即，使你剩余钱数最多的最短路径)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Set states(i,j) as unvisited for all (i,j)
Set Min[i][j] to Infinity for all (i,j)
Min[0][M] = 0
while(true){
	// Among all unvisited states(i,j) find the one for which Min[i][j] is the smallest. Let this state found be (k,l).
// If there wasn't found any state (k,l) for which Min[k][l] is less than Infinity - exit While loop.
// Mark state(k,l) as visited
	For All Neighbors p of Vertex k
		if(l - S[p]>=0 && Min[p][l-S[p]]>Min[k][l]+Dist[k][p])
			Min[p][l-S[p]]=Min[k][l]+Dist[k][p]
	
	/* If for state(i,j) there are enough money left for going to vertex p, (l-S[p] represents the money that will remain after passing to vertex p), and the shortest path found for state(p,l-S[p]) is bigger than [the shortest path found for state(k,l)] + [distance from vertex k to vertex p)], then set the shortest path for state(i,j) to be equal to this sum. */
	End For
End While
/* Find the smallest number among Min[N-1][j] (for all j, 0<=j<=M); if there are more than one such states, then take the one with greater j. If there are no states(N-1,j) with value less than Infinity - then such a path doesn't exist. */

高级问题

需要仔细的揣摩才能将其规约为可用DP解的问题。

给定一个M行N列的矩阵(M*N个格子)，每个格子中放着一定数量的苹果。 你从左上角的格子开始，只能向下或向右走，目的地是右下角的格子。 你每走过一个格子，就把格子上的苹果都收集起来。然后你从右下角走回左上角的格子， 每次只能向左或是向上走，同样的，走过一个格子就把里面的苹果都收集起来。 最后，你再一次从左上角走到右下角，每过一个格子同样要收集起里面的苹果 (如果格子里的苹果数为0，就不用收集)。求你最多能收集到多少苹果。

注意：当你经过一个格子时，你要一次性把格子里的苹果都拿走。

限制条件：1 < N, M <= 50；每个格子里的苹果数量是0到1000(包含0和1000)。

太难了不会做T_T