资源描述：
《浙江省选一试讲课素材学习资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、浙江省选一试讲课素材动态规划前的准备工作求斐波那契数列。现有f[0]=f[1]=1,且f[i]=f[i-1]+f[i-2],求f[n]。怎么做呢根据题目意思，设计函数。intf(intx){returnx<=1?1:f(x-1)+f(x-2);}优化然而用这种方法效率是极低的。大家不妨分析一下复杂度。O(n)=O(n-1)+O(n-2)。因此我们要计算f[n]时，它的时间复杂度也是O(f[n])的。这里我们要引入一个记忆化搜索的概念。记忆化搜索我们发现对于一个值f(x)它一定不会改变。但是我们在计算f(5
2、)的过程中需要计算f(4)与f(3)，而在计算f(4)的过程中又需要计算f(3)，这里f(3)就被计算了两次。怎么优化呢。为了避免这种重复运算。我们可以开一个数组fib来记录已经知道的值。即intf(x){returnfib[x]?fib[x]:fib[x]=f(x-1)+f(x-2);}这里要注意在调用f数组之前我们就需要将fib[0]和fib[1]设初始值1。我们再来分析一下复杂度。对于每个f(x)，只会被f(x+1)与f(x+2)调用一次，这样就是线性啦！另一种计算方法在上述运算过程中，我们要知道f
3、(x)的值需要从前面调用。我们不妨从前往后计算f(x)。即f[x]=f[x-1]+f[x-2]。这样f[n]就是第n项斐波那契数列啦！动态规划在刚才的题目中，从某种意义上来说，虽然已经有了阶段，但还不是真正的动态规划。动态规划的两个基本特征：一、重叠子问题。二、最优子结构。然而在刚刚的题目中，仅仅只有重叠子问题，我们可以称之为递推！接下来我们来看一道较难的动态规划题。吃金币游戏在一个n*m的网格中，第i行第j列有ai,j(ai,j>0)个金币。lyk要从(1,1)走到(n,m)且只能向右或者下走，问它最多
4、能收集多少金币。吃金币游戏我们来看如何用搜索来做出这个题目。令函数f(x,y)表示从(1,1)走到(x,y)最多能收集多少金币。那么有intf(intx,inty){returnmin(x,y)==0?0:a[x][y]+max(f(x-1,y),f(x,y-1));}其中min和max分别表示最小值和最大值。记忆化搜索然而我们发现这样子的搜索效率是极低的。不妨来分析一下复杂度。O(n,m)=O(n-1,m)+O(n,m-1)。O(0,i)=O(i,0)=1。实际上O(n,m)就相当于是从(1,1)走到（
5、n,m）的路径条数，共C(n+m-2,n-1)的复杂度。那么如果我们使用记忆化搜索呢？令dp[n][m]来记录从(1,1)走到(n,m)的最大值。即有intf(intx,inty){returndp[x][y]?dp[x][y]:dp[x][y]=max(f(x-1,y),f(x,y-1))+a[x][y];}注意边界。这样就能使复杂度降低至O(nm)级别啦。动态规划我们不妨按顺序来做。即for(i=1;i<=n;i++)for(j=1;j<=m;j++)dp[i][j]=max(dp[i-1][j],d
6、p[i][j-1])+a[i][j];这样就有一个最优子结构在里面啦！这就是一个最简单的动态规划。练习题1给定一个长度为n的仅包含左括号或问号的字符串，将问号变成左括号或右括号使得该括号序列合法，求方案总数。例如(())与()()都是合法的括号序列。n<=3000。做动态规划题的一般步骤先写出最简单的搜索。改成记忆化搜索。改变顺序变成循环的形式，写出动态规划的状态和转移。就做完啦！练习题1考虑到大家都是来参加省选的，应该有相当高的水平。我就直接略过前两个步骤啦！令dp[i][j]表示当前到第i个字符，现在
7、还有j个左括号。那么分两种情况考虑。若第i+1个字符是左括号，则能转移到dp[i+1][j+1]。若第i+1个字符是问号，则能转移到dp[i+1][j-1]与dp[i+1][j+1]。最终dp[n][0]就是方案总数啦。时间复杂度为O(n^2)。优化当n高达10W时怎么办呢？状态可以通过滚动数组滚动掉一维。至今仍然还找不到一个理论时间复杂度能通过时限的算法。不过可以通过卡常数，使得在不到4s内出解。练习题2给定n个由左右括号组成的字符串。选择其中若干字符串，使得组成一个合法的括号序列且长度最长。n<=10
8、00，Σ
9、si
10、<=10000。一个例子：()、(()、)答案是6，能组成(())()练习题2考虑一个合法括号序列的组成方案。一定不存在某个位置右括号个数大于左括号个数的情况。每个括号序列可以形象地表示成3个参数。将其中合法的括号删除后，只有可能是左边若干右括号，右边若干左括号，并记录其长度。练习题2我们将左括号个数大于等于右括号个数的提取出来，表示加入该括号序列后，能增加左括号与右括号的差值。对于这些括号序列，将它们按照右括
