题目分析

琪儿有一堆书，每本书有不同的宽度和高度。她已经将书按高度从低到高排列，但由于每本书的宽度不一致，书架看起来很不整齐。她希望通过去掉一些书来最小化书架的“不整齐度”。

不整齐度的定义为：​每两本书宽度差的绝对值的和​。例如，给定一组书的宽度：[2, 4, 1, 3]，其不整齐度计算为：

|2 - 4| + |4 - 1| + |1 - 3| = 2 + 3 + 2 = 7

我们的目标是去掉 k 本书，剩下的书能使得不整齐度最小。 设f[i][j]表示在选第i本书留下的情况下，前i本书选j本书的最优值，如图所示，显然f[i][j]的值可以由前x本书选了j-1本书的情况下加上第i本书推得。

所以，设w[i]为第i本书的宽度，动态转移方程为：

f[i][j]＝min{f[x][j-1]＋abs(w[x]-w[i])} (1≤i≤n，2≤j≤min{i,n-k},j-1≤x≤i-1)

解决思路

1. ​去掉 k 本书​：我们希望从所有的书中选择 n - k 本书，使得它们的宽度差的和最小。问题转化为在 n 本书中选择 n - k 本，使得选出的书的宽度差最小。
2. ​动态规划 (DP) 解法​：
   • 我们定义 dp[i][j] 表示前 i 本书中选择 j 本书的最小不整齐度。
   • ​状态转移​：如果我们选择第 i 本书，则 dp[i][j] 的值可以由前面的 x 本书选择 j - 1 本书并加上当前的差值推导出来。
   • 最终，我们需要找到 dp[n][n-k]，即选出 n - k 本书时的最小不整齐度。
3. ​逆向思维​：由于题目说“直接从去掉多少书来划分阶段是没有思路的”，我们可以采用逆向思维来解题。即，我们从选出 n - k 本书开始，逐步推导出最优解。
4. ​优化​：我们可以通过合适的状态转移和前缀和的技巧来优化计算，减少不必要的重复计算。

时间复杂度

• ​时间复杂度​：O(n^2)，因为我们需要遍历 n 本书，每本书都可能与前面的书进行比较来更新 dp。
• ​空间复杂度​：O(n^2)，用于存储 DP 数组。

示例

​输入​：

5 2
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

​输出​：

249

​解释​：

• 去掉 2 本书后，选择合适的书放在书架上，最小的不整齐度为 249。