动态规划算法学习

http://blog.csdn.net/nevasun/article/details/6977511

         笔试面试中经常会出现一些考察动态规划方面的题目,以前没有接触过,现在初学做个整理。

1. 什么是动态规划?          和分治法一样,动态规划(dynamicprogramming)是通过组合子问题而解决整个问题的解。          分治法是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解。          动态规划适用于子问题不是独立的情况,也就是各子问题包含公共的子子问题。          此时,分治法会做许多不必要的工作,即重复地求解公共的子问题。动态规划算法对每个子问题只求解一次,将其结果保存起来,从而避免每次遇到各个子问题时重新计算答案。 2. 动态规划算法的设计 两种方法:          自顶向下(又称记忆化搜索、备忘录):基本上对应着递归函数实现,从大范围开始计算,要注意不断保存中间结果,避免重复计算          自底向上(递推):从小范围递推计算到大范围 动态规划的重点:          递归方程+边界条件 3. 爬楼梯问题          一个人每次只能走一层楼梯或者两层楼梯,问走到第80层楼梯一共有多少种方法。          设DP[i]为走到第i层一共有多少种方法,那么DP[80]即为所求。很显然DP[1]=1, DP[2]=2(走到第一层只有一种方法:就是走一层楼梯;走到第二层有两种方法:走两次一层楼梯或者走一次两层楼梯)。同理,走到第i层楼梯,可以从i-1层走一层,或者从i-2走两层。很容易得到:          递推公式:DP[i]=DP[i-1]+DP[i-2]          边界条件:DP[1]=1   DP[2]=2          (a)自顶向下的解法:

[cpp] view plaincopy

 long long dp[81] = {0};/*用于保存中间结果 
 否则会重复计算很多重复的子问题*/ 
 long long DP(int n)  
 {  
  if(dp[n])  
  return dp[n];  
  if(n == 1)  
  return 1;  
  if(n == 2)  
  return 2;  
     dp[n] = DP(n-1) + DP(n-2);  
  return dp[n];     
 }  

         (b)自底向上的解法:

[cpp] view plaincopy

 int i;  
 long long dp[81]; /* 注意当n超过75时,结果值将超过int范围 */ 
 dp[1] = 1;  
 dp[2] = 2;  
 for(i=3; i <= 80; i++)  
     dp[i] = dp[i-1] + dp[i-2];  

4. 最长上升子序列          对于序列:4 1 2 24,它的最长上升子序列是1 2 4,长度为3。          对于序列:4 2 4 25 6,它的最长上升子序列是2 4 5 6,长度为4          设a[i]表示原序列,设DP[i]表示以第i个数结尾的最长上升序列的长度,那么很显然想导出DP[i]的值,需要在DP[k](1<=k<i)中找出满足a[k]<a[i]最大的一项。假设第kk项是我们找到的答案,那么第i个数就可以接在第kk个数之后,成为以第i个数结尾的最长升序列。如果没有找到答案,换言之第i个数比前面的数都要小,那么DP[i]=1,也即生成了从自己开始又以自己结尾的最长升序列。综上,我们很容易得出:          递推公式:DP[i]=max(DP[k]+1,DP[i])  1<=k<i          边界条件:DP[i]=1                   1<=i<=n          算法复杂度为O(n^2)

[cpp] view plaincopy

 void RiseSequence(int Array[], int num)  
 {  
 #define MAX_LENGTH  30 
  struct 
     {  
  int SequenceValue;  /* max length ending with this num */ 
  int PreviousIndex;  /* record the previous number */ 
     }ArrayInfo[MAX_LENGTH], temp;  
  int i;  
  for(i = 0; i < num; i++)  
     {  
  int j;  
         ArrayInfo[i].SequenceValue = 1;  
         ArrayInfo[i].PreviousIndex = -1;  
  for(j = 0; j < i; j++)  
         {  
  if(Array[j] < Array[i] && (ArrayInfo[j].SequenceValue + 1 > ArrayInfo[i].SequenceValue))  
             {  
                 ArrayInfo[i].SequenceValue = ArrayInfo[j].SequenceValue + 1;  
                 ArrayInfo[i].PreviousIndex = j;  
             }  
         }  
     }  
     temp.SequenceValue = ArrayInfo[0].SequenceValue;  
  for(i = 1; i < num; i++)  
     {  
  if(temp.SequenceValue < ArrayInfo[i].SequenceValue)  
         {  
             temp.SequenceValue = ArrayInfo[i].SequenceValue;  
             temp.PreviousIndex = i;  
         }  
     }  
  for(i = 0; i < temp.SequenceValue; i++)  
     {  
         printf("%d  ", Array[temp.PreviousIndex]);  /* in reverse order */ 
         temp.PreviousIndex = ArrayInfo[temp.PreviousIndex].PreviousIndex;  
     }  
     printf("\nthe max rising sequence length is %d\n", temp.SequenceValue);  
 }  

5. 最长公共子序列          给定两个序列X和Y,称序列Z是X和Y的公共子序列如果Z既是X的一个子序列,又是Y的一个子序列。例如,如果X={a,b,c,b,d,a,b} Y={b,d,c,a,b,a} 那么序列{b,c,a}就是X和Y的一个公共子序列,但是它并不是X和Y的最长公共子序列,因为它的长度为3。而同为X和Y公共子序列的{b,c,b,a},长度为4,因为找不到长度为5或更大的公共子序列,所以X和Y的最长公共子序列长度就为4。          假设两个序列数组分别为a,b。定义f(i,j)为计算到a数组第i个数、b数组第j个数时所得到的最长公共子序列的长度。这时有两种情况:          1.假如a[i]=b[j],那么f(i,j)=f(i-1,j-1)+1          2.假如a[i]!=b[j],那么f(i,j)=max(f(i-1,j),f(i,j-1))          边界条件为:f(i,0)=0     1<=i<=len(a)                                f(0,j)=0     1<=j<=len(b)          算法复杂度:O(n^2),len(a)表示数组a的长度。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏儿童编程

天干地支五行八卦的对应关系

18890
来自专栏儿童编程

我不是算命先生,却对占卜有了疑惑——如何论证“占卜前提”的正确与否

事出有因,我对《周易》感兴趣了很多年。只是觉得特别有趣,断断续续学习了一些皮毛。这几天又偶然接触到了《梅花易数》,觉得很是精彩,将五行八卦天干地支都串联了起来。...

14010
来自专栏儿童编程

一张图理清《梅花易数》梗概

学《易经》的目的不一定是为了卜卦,但是了解卜卦绝对能够让你更好地了解易学。今天用一张思维导图对《梅花易数》的主要内容进行概括,希望能够给学友们提供帮助。

30940
来自专栏儿童编程

儿童创造力教育与编程教育的碰撞——MIT雷斯尼克教授最新理论梗概

儿童编程教育已经在我国各一线二线城市疯狂出现,颇有“烂大街”的趋势。我们不禁要问很多很多问题:

21870
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.1K20
来自专栏儿童编程

《动物魔法学校》儿童学编程Scratch之“外观”部分

导读:本文通过一个案例《动物魔法学校》来学习Scratch语言的“外观”部分。之后通过一系列其他功能的综合运用对作品功能进行了扩展。

18640
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

17430
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

26840
来自专栏儿童编程

声音功能让儿童编程更有创造性

导读:Scratch中声音功能非常强大,除了常规的音效,你甚至可以模拟各种乐器的各个发音、设置节拍、休止……如果你愿意,甚至可以用它创作一个交响乐。我们可以引导...

13540
来自专栏儿童编程

什么样的人生才是有意义的人生——没有标准的标准答案

【导读】其实我们可以跳出这个小圈圈去更加科客观地看一下这个世界。在夜晚的时候我们仰望天空,浩瀚的宇宙中整个地球只是一粒浮尘,何况地球上一个小小的人类?在漫长的历...

1.7K50

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励