时间戳

首页 > 技术文章 > 算法第三章作业

算法第三章作业

lqx739744996 2019-10-27 18:35 原文

 

一. 对动态规划算法的理解

动态规划算法类似于递归算法，但递归时常会出现冗杂繁重且庞大的计算量，程序运行的速度也比较慢。进行动态规划算法使用时一般都需列出递归方程，然后分成子问题，分析最优解，大大降低了时间复杂度；类比分治法，此处的子问题并非毫无关联，而是一个问题的解是根据已经得到的另一子问题的解得到

课本所示动态规划算法的步骤大概分成四步：

（1）找出最优解的性质，并刻画其结构特征

（2）递归地定义最优值

（3）以自底向上的方式计算最优值

（4）根据计算最优值时得到的信息构造最优解

2. 分别列出编程题1、2的递归方程

第一题递归部分的代码：

 1 　　for(int i=1;i<n;i++){
 2         for(int j=0;j<i;j++){
 3             if(a[i]>a[j]&&max[i]<max[j]+1){
 4                 max[i]=max[j]+1;
 5             }
 6         }
 7     }
 8     int MAX=0;
 9     for(int i=0;i<n;i++){
10         if(MAX<max[i])
11         MAX=max[i];
12     }

第二题递归部分代码：

 1     for(int i=2;i<=n;i++)
 2     {
 3         for(int j=i+1;j<=n;j++)
 4         {
 5             int k=j-i;
 6             for(int p=k;p<j;p++)
 7             {
 8                 if(cost[k][j]>cost[k][p]+cost[p][j])
 9                 cost[k][j]=cost[k][p]+cost[p][j];
10             }
11         }
12     }

3. 说明结对编程情况

第一二题上课老师讲了之后我们换了个方法重新打了一遍，比较简单能够实现，但是第三题挖地雷的题讨论了很久且有出现答案正确但是不能在PTA中通过的情况，最终还是成功通过了，结队的效率一定上集合了两个人的想法，做题效率更高、打代码途中出现的问题也能迅速纠正。

 

推荐阅读