分治和动态规划：共同点：两者都是把大问题转换成小问题/子问题来解决，并且当最优子问题组合成最优大问题，关键点在于找到子问题的划分。不同点：分治采用递归写法，当子问题之间没有重复的时候，是很好的方法，但当子问题之间存在重复的时候，分治方***重复计算子问题很多次，碰到一次算一次，因为分治是自上而下的，往下走的过程中，每次碰到相同的子问题都要重复计算，时间复杂度很高。动态规划，专门针对这种存在重复子问题的分解算法，并且每一个大问题都可以由它的子问题的最优解来表示；因此，动态规划采用自下而上的方法，先计算最小的子问题的最优解，再一层层组合成大问题的最优解，计算过程中不存在子问题的重复计算。

voidbinarysearchtree(inta[],intb[],intn,int**m,int**s,int**w){inti,j,k,t,l;for(i=1;i<=n+1;i++){w[i][i-1]=a[i-1];m[i][i-1]=0;}for(l=0;l<=n-1;l++)//----l是下标j-i的差for(i=1;i<=n-l;i++){j=i+l;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i][i-1]+m[i+1][j]+w[i][j];s[i][j]=i;for(k=i+1;k<=j;k++){t=m[i][k-1]+m[k+1][j]+w[i][j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}