算法第3章作业

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

动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解

有最优子结构性质和重叠子问题性质的问题，就可以用动态规划算法

设计算法的步骤是 ①分析最优解的结构 ②建立递归方式（关键） ③计算最优值 ④构造最优解

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

编程题1  思路：求原序列a与原序列的递增序列b的最长公共子序列

            0,    i=0,j=0

c[i][j]={ c[i-1][j-1]+1,    a[i]=b[j]

            max(c[i-1][j],c[i][j-1])

编程题2   思路： 类似最短路径的迪杰斯特拉算法

for(int i=2;i<n;i++){
     int min=999999999; int k=0;
     for (int j=2;j<=n;j++){ if(a[1][j]<min&&b[1][j]==0) {min=a[1][j]; k=j;}
     }
     b[1][k]=1;
     for(int w=k+1;w<=n;w++) {
     
     if(a[1][k]+a[k][w]<a[1][w]) a[1][w]=a[1][k]+a[k][w];}
    }
 3.说明结对编程情况

我主要负责审题和打代码，打完代码交给另外一位同学找bug 

找出bug再进行修改，不断完善代码，通过结对编程可以将程序变得更完善

算法第3章作业

原文：https://www.cnblogs.com/iamrounan/p/9861377.html