解题思路
给定长度为 n 的数组，需要把它划分为 m 个连续区间，使所有区间的“价格波动值”(区间内最大值减最小值)之和最小。
这是一类典型的“划分型动态规划(Partition DP)”问题。
状态设计
- 设
dp[i][k] 表示把前 i 个元素划分成 k 个连续区间时的最小代价。
- 转移：最后一个区间如果是
(j+1 … i)，则
P4243.第1题-促销价格波动值
题目内容
某超市有一排 n 个连续的货架，每个货架上摆放的商品有一个单价。超市计划将这排货架分成 m 个连续的促销区域。
每组区域是连续的货架区间，例如可以是第 2−5 个货架,但不能是第 2−3 个和第 5 个货架。
每个促销区域的“价格波动值”定义为该区域内商品单价的最大值减去最小值。特别地，如果单独一个货架成为促销区域，那么它的价格波动值为 0 。
超市希望所有促销区域的价格波动值之和最小，以此吸引更多顾客。请你帮助他们计算将 n 个货架分成 m 个连续区域后，价格波动值之和的最小值。
输入描述
第一行包含两个整数 n 和 m ，分别表示货架的总数和要分成的区域数量.
第二行包含 n 个整数 a ,依次表示从左到右每个货架上商品的单价。
1<=m<=n<=500,1<=ai<=1,000,000,000.
输出描述
一行，一个整数,表示所有区域的价格波动值之和的最小值.
样例1
输入
4 2
3 1 4 2
输出
3
说明
其中一种可行的方法为:将第一个货架分为一个促销区域，将后三个货架分为一个促销区域。促销区 1 的价格波动值为 0 ，促销区 2 的价格波动值为 3 ，波动值总和为 3 .
可以证明没有其他方案可以使波动值总和更小。
