解题思路
给定长度为 n 的数组，需要把它划分为 m 个连续区间，使所有区间的“波动值”(区间内最大值减最小值)之和最小。
这是一类典型的“划分型动态规划(Partition DP)”问题。
状态设计
- 设
dp[i][k] 表示把前 i 个元素划分成 k 个连续区间时的最小代价。
- 转移：最后一个区间如果是
(j+1 … i)，则
题目内容
在通信系统中，有一串长度为 n 的信号序列，需要将其划分为 m 个连续的时间片段。每个片段由连续的信号采样点组成。片段的“波动值”定义为片段内信号值的最大值与最小值的差；若片段仅包含一个采样点，波动值为 0。要求所有片段的波动值之和最小。请你计算这个最小总波动值。
序列长度 n 和片段数 m 满足 1≤m≤n≤500，每个信号值均为不超过 109 的正整数。
输入描述
第一行包含两个整数 n 和 m，分别表示信号序列的长度和需要划分的片段数量。
第二行包含 n 个整数，依次表示信号序列中每个采样点的值。
输出描述
