贪心是局部最优解,只能保证局部最优,不能保证全局最优,不能用贪心做。
思路:最后一次合并一定是两堆最小合并代价+所有石子的代价,这两堆是[1,k][k+1,n],k可能是1~n中的任意一个数,假设我们知道k是多少,那么,问题转化成求[1,k]和[k+1,n]的最小合并代价,.......当石子剩余2时,递推回去就可求解了。但是,还有一个问题,去选出k,我们可以遍历当前所求区间每一种k的取值,然后选出最小值。
以我目前菜鸡的理解水平,dp就是上述内容倒着看,我们先求出所有递归的结束条件,然后再去求上一层......。但是与递归最大的差别就是不会求重复数据,这样就会降低时间复杂度。
#include
若有问题,请各位大佬积极指正。