解题思路
给定长度为 n 的数组，需要把它划分为 m 个连续区间，使所有区间的“价格波动值”(区间内最大值减最小值)之和最小。
这是一类典型的“划分型动态规划(Partition DP)”问题。
状态设计
- 设
dp[i][k] 表示把前 i 个元素划分成 k 个连续区间时的最小代价。
- 转移：最后一个区间如果是
(j+1 … i)，则
题目内容
某超市有一排 n 个连续的货架，每个货架上摆放的商品有一个单价。超市计划将这排货架分成 m 个连续的促销区域。
每组区域是连续的货架区间，例如可以是第 2−5 个货架,但不能是第 2−3 个和第 5 个货架。
