第三章作业

1  对动态规划的基本思想是将待求的问题分解成若干个子问题，通过子问题的解得到原问题的解。然后为了避免大量的重复计算，可用一个表记录已解决问题的答案。动态规划将原来具有指数级时间复杂度算法改进成了具有多项式时间复杂度的算法，减低其时间复杂度。但它在实现的过程中，不得不存储产生过程中的各种状态，会增加空间复杂度。

2

7—1：b[i]=b[k]+1;(k为最大小于i的数的下标）

for(int i=1;i<n;i++){
int max=0;
for(int k=0;k<i;k++){
if(a[k]<a[i]&&b[k]>max){
max=b[k];
}
b[i]=max+1;
}
}

7—2：r[1][n]=min{r[1][k]+r[k][n]} (1 < k <n)   当n=1时，r[1][n]=0

for(int i=2;i<=n;i++){
for(int j=i+1;j<=n;j++){
int k=j-i;
for(int p=k;p<j;p++){
if(r[k][p]+r[p][j]<r[k][j]){
r[k][j]=r[k][p]+r[p][j];
}
}
}
}

3 这次作业的完成主要靠自己独立思考与看书，与队友交流较少

第三章作业

原文：https://www.cnblogs.com/halo1234/p/9898353.html