算法第三章作业

时间:2021-06-10 16:36:28

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

如书上写的,动态规划算法与分治算法类似,基本思想也是将问题划分为若干子问题再进行求解。我个人理解中,动态规划算法在进行问题的分解时,会选择一条最优解答路线来将重复的问题通过同样的代码进行实现,免去了冗杂的重复代码。所以时常看到的动态规划算法都会显得十分的“精妙”。动态规划算法中使用的备忘录也是在之前的代码编写中使用过的,但是将其归类为一种方法,一种节约运算量的方法还是第一次了解,这样的做法使得代码有了很高的效率。

2.递归方程

编程题1:主要思想是将原数组a1通过排序变成有序数列a2,再求a1和a2的LCS。因此递归方程为LCS的递归方程:c[i][j] = max{c[i][j-1], c[i-1][j]}. i,j>0;xi!=yi。

编程题2:c[i][j] = min {c[i][k]+c[k][j]}。

3.结对编程情况:

同上周一样,两人都不是擅长协助的人,但是更加频繁的进行想法的交流,使得编程过程更加的简单了。