题目传送门 分析 此题做法有好几种，其中一种是 dp，还有一种是记忆化搜索。 我们知道暴力 dfs 非常慢，但是加上记忆化优化后会原地起飞。 dfs(l,r)表示合并区间 [ l , r ] [l,r] [l,r] 的最小价值，那么我们枚举 [ l , r ] [l,r] [l,r] 间的一个中转点 i i i，答案就是： 不合并；合并，加上代价； 取最小值。 dfs(l,r)

思路：区间DP 首先这其实是一个模板题，其次，这道题可能有人会觉得简单，但是我还是需要讲一下具体的思路，以方便自己的理解，和新手的初学。 对于一堆石子来说，我们需要知道，怎么样才能使这种代价变得最小，也就是在相邻的石子堆之中，我们需要遍历每一个区间，也就是区间的长度最多是N,意思也就是我们需要遍历这区间当中的每一个子区间，然后再一个一个去选，把全部的结果罗列出来之后我们才能知道这里的最佳答案在

区间动态规划-石子合并 欢迎关注公众号【比特正传】，后期会分享更多c++、数据结构和算法相关内容。