算法 第三章作业

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

动态规划是针对一类求最优解的问题的算法， 其核心是将一个问题分解成为若干个子问题， 部分类似于分治的思想（参考归并排序），分治会产生重复计算子问题以至于耗费更多的时间的问题，而动态规划算法能用一个表保留解决问题的子答案，在需要时再找出已求得的答案可以避免大量重复计算， 通过求每一次的最优决策， 来得到一个最优解。在这里最重要的就是子问题的思想。

2.列出编程1.2题的递归方程

1）

if (a[j] < a[i]&& b[j]>b[i] - 1) {
b[i] = b[j] + 1;}

//然后定义t=b[1]

if (b[k] > t) {
t = b[k];}

2）

for(k=i;k<=j;k++) { //找出某一站k，使r(i,k)+r(k,j)最小 
min=a[i][k]+a[k][j];
if(a[i][j]>min) {
a[i][j]=min;}
}

3.结对编程情况

此次结对编程时间用得比上次要长些，在理解清楚题目的意思之后，顺着题目的思路一步步解题，在编程过程中对动态规划算法更加地了解了，而在意见产生分歧时，可以进行时间复杂度和空间复杂度的分析已达到更好的编程效果。在结对编程过程中逻辑思维，判断思维也得到了一定的锻炼。

算法 第三章作业

原文：https://www.cnblogs.com/VKookie/p/9904765.html