《电子商务网站开发与管理》,遂平网站建设,秸秆可以发酵吗网站建设吗,蚌埠北京网站建设前言_我们遇到的问题中#xff0c;有很大一部分可以用动态规划(简称DP)来解。 解决这类问题可以很大地提升你的能力与技巧#xff0c;我会试着帮助你理解如何使用DP来解题。 这篇文章是基于实例展开来讲的#xff0c;因为干巴巴的理论实在不好理解。注意#xff1a;如果你对…前言_我们遇到的问题中有很大一部分可以用动态规划(简称DP)来解。 解决这类问题可以很大地提升你的能力与技巧我会试着帮助你理解如何使用DP来解题。 这篇文章是基于实例展开来讲的因为干巴巴的理论实在不好理解。注意如果你对于其中某一节已经了解并且不想阅读它没关系直接跳过它即可。简介(入门)什么是动态规划我们要如何描述它?动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度 因此它比回溯法、暴力法等要快许多。现在让我们通过一个例子来了解一下DP的基本原理。首先我们要找到某个状态的最优解然后在它的帮助下找到下一个状态的最优解。“状态”代表什么及如何找到它?“状态”用来描述该问题的子问题的解。原文中有两段作者阐述得不太清楚跳过直接上例子。如果我们有面值为1元、3元和5元的硬币若干枚如何用最少的硬币凑够11元 (表面上这道题可以用贪心算法但贪心算法无法保证可以求出解比如1元换成2元的时候)首先我们思考一个问题如何用最少的硬币凑够i元(i11)为什么要这么问呢 两个原因1.当我们遇到一个大问题时总是习惯把问题的规模变小这样便于分析讨论。 2.这个规模变小后的问题和原来的问题是同质的除了规模变小其它的都是一样的 本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。好了让我们从最小的i开始吧。当i0即我们需要多少个硬币来凑够0元。 由于135都大于0即没有比0小的币值因此凑够0元我们最少需要0个硬币。 (这个分析很傻是不是别着急这个思路有利于我们理清动态规划究竟在做些什么。) 这时候我们发现用一个标记来表示这句“凑够0元我们最少需要0个硬币。”会比较方便 如果一直用纯文字来表述不出一会儿你就会觉得很绕了。那么 我们用d(i)j来表示凑够i元最少需要j个硬币。于是我们已经得到了d(0)0 表示凑够0元最小需要0个硬币。当i1时只有面值为1元的硬币可用 因此我们拿起一个面值为1的硬币接下来只需要凑够0元即可而这个是已经知道答案的 即d(0)0。所以d(1)d(1-1)1d(0)1011。当i2时 仍然只有面值为1的硬币可用于是我拿起一个面值为1的硬币 接下来我只需要再凑够2-11元即可(记得要用最小的硬币数量)而这个答案也已经知道了。 所以d(2)d(2-1)1d(1)1112。一直到这里你都可能会觉得好无聊 感觉像做小学生的题目似的。因为我们一直都只能操作面值为1的硬币耐心点 让我们看看i3时的情况。当i3时我们能用的硬币就有两种了1元的和3元的( 5元的仍然没用因为你需要凑的数目是3元5元太多了亲)。 既然能用的硬币有两种我就有两种方案。如果我拿了一个1元的硬币我的目标就变为了 凑够3-12元需要的最少硬币数量。即d(3)d(3-1)1d(2)1213。 这个方案说的是我拿3个1元的硬币第二种方案是我拿起一个3元的硬币 我的目标就变成凑够3-30元需要的最少硬币数量。即d(3)d(3-3)1d(0)1011. 这个方案说的是我拿1个3元的硬币。好了这两种方案哪种更优呢 记得我们可是要用最少的硬币数量来凑够3元的。所以 选择d(3)1怎么来的呢具体是这样得到的d(3)min{d(3-1)1, d(3-3)1}。OK码了这么多字讲具体的东西让我们来点抽象的。从以上的文字中 我们要抽出动态规划里非常重要的两个概念状态和状态转移方程。上文中d(i)表示凑够i元需要的最少硬币数量我们将它定义为该问题的”状态” 这个状态是怎么找出来的呢我在另一篇文章动态规划之背包问题(一)中写过 根据子问题定义状态。你找到子问题状态也就浮出水面了。 最终我们要求解的问题可以用这个状态来表示d(11)即凑够11元最少需要多少个硬币。 那状态转移方程是什么呢既然我们用d(i)表示状态那么状态转移方程自然包含d(i) 上文中包含状态d(i)的方程是d(3)min{d(3-1)1, d(3-3)1}。没错 它就是状态转移方程描述状态之间是如何转移的。当然我们要对它抽象一下d(i)min{ d(i-vj)1 }其中i-vj 0vj表示第j个硬币的面值;有了状态和状态转移方程这个问题基本上也就解决了。当然了Talk is cheap,show me the code!伪代码如下Python代码如下import osMin[x for x in range(12)];VN[1,3,5];for i in range(1,12,1):for j in range(3):if VN[j]i and Min[i-VN[j]]1Min[i]Min[i-VN[j]]1;print(Min[1::1]);下图是当i从0到11时的解从上图可以得出要凑够11元至少需要3枚硬币。此外通过追踪我们是如何从前一个状态值得到当前状态值的 可以找到每一次我们用的是什么面值的硬币。比如从上面的图我们可以看出 最终结果d(11)d(10)1(面值为1)而d(10)d(5)1(面值为5)最后d(5)d(0)1 (面值为5)。所以我们凑够11元最少需要的3枚硬币是1元、5元、5元。注意原文中这里本来还有一段的但我反反复复读了几遍 大概的意思我已经在上文从i0到i3的分析中有所体现了。作者本来想讲的通俗一些 结果没写好反而更不好懂所以这段不翻译了。初级上面讨论了一个非常简单的例子。现在让我们来看看对于更复杂的问题 如何找到状态之间的转移方式(即找到状态转移方程)。 为此我们要引入一个新词叫递推关系来将状态联系起来(说的还是状态转移方程)OK上例子看看它是如何工作的。一个序列有N个数A[1],A[2],…,A[N]求出最长非降子序列的长度。 (讲DP基本都会讲到的一个问题LISlongest increasing subsequence)正如上面我们讲的面对这样一个问题我们首先要定义一个“状态”来代表它的子问题 并且找到它的解。注意大部分情况下某个状态只与它前面出现的状态有关 而独立于后面的状态。让我们沿用“入门”一节里那道简单题的思路来一步步找到“状态”和“状态转移方程”。 假如我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度其中i为了方便理解我们是如何找到状态转移方程的我先把下面的例子提到前面来讲。 如果我们要求的这N个数的序列是534867根据上面找到的状态我们可以得到(下文的最长非降子序列都用LIS表示)前1个数的LIS长度d(1)1(序列5)前2个数的LIS长度d(2)1(序列33前面没有比3小的)前3个数的LIS长度d(3)2(序列344前面有个比它小的3所以d(3)d(2)1)前4个数的LIS长度d(4)3(序列3488前面比它小的有3个数所以 d(4)max{d(1),d(2),d(3)}13)OK分析到这我觉得状态转移方程已经很明显了如果我们已经求出了d(1)到d(i-1) 那么d(i)可以用下面的状态转移方程得到d(i) max{1, d(j)1},其中j用大白话解释就是想要求d(i)就把i前面的各个子序列中 最后一个数不大于A[i]的序列长度加1然后取出最大的长度即为d(i)。 当然了有可能i前面的各个子序列中最后一个数都大于A[i]那么d(i)1 即它自身成为一个长度为1的子序列。分析完了上图(第二列表示前i个数中LIS的长度 第三列表示LIS中到达当前这个数的上一个数的下标根据这个可以求出LIS序列)Talk is cheap, show me the code:#include using namespace std;int lis(int A[], int n){int *d new int[n];int len 1;for(int i0; in; i){d[i] 1;for(int j0; ji; j)if(A[j]A[i] d[j]1d[i])d[i] d[j] 1;if(d[i]len) len d[i];}delete[] d;return len;}int main(){int A[] {5, 3, 4, 8, 6, 7};coutlis(A, 6)endl;return 0;}Python 代码如下import sysdef lis(*args,num1):d[0]*num;len_num1;for i in range(num):d[i]1;for j in range(i):if args[j]args[i] and d[i]d[i]d[j]1;if d[i]len_num:len_numd[i];return len_num;print(lis(5,3,4,8,6,7));该算法的时间复杂度是O(n2 )并不是最优的解法。 还有一种很巧妙的算法可以将时间复杂度降到O(nlogn)网上已经有各种文章介绍它 这里就不再赘述。传送门 LIS的O(nlogn)解法。 此题还可以用“排序LCS”来解感兴趣的话可自行Google。练习题无向图G有N个结点(1提示在每一步中对于那些没有计算过的结点 及那些已经计算出从结点1到它的最短路径的结点如果它们间有边 则计算从结点1到未计算结点的最短路径。尝试解决以下来自topcoder竞赛的问题ZigZag – 2003 TCCC Semifinals 3BadNeighbors – 2004 TCCC Round 4FlowerGarden – 2004 TCCC Round 1转载自http://www.hawstein.com/posts/dp-novice-to-advanced.html
