基于成本的数组最优多分割算法求解，适配MIDI吉他指法拆分场景

解法思路 #

1. 动态规划（最推荐的常规解法） #

这个问题本质是带权重的最优序列分割问题，结合你的吉他指法场景限制，完全可以用动态规划在多项式时间内求解，不需要上NP问题的复杂求解方案：

• 状态定义：设dp[i]为处理完前i个事件（对应原数组下标0到i-1）时的最小总成本，数组prev[i]用来记录到达i位置的最优前序分割点，方便最后回溯得到分割索引。
• 初始条件：dp[0] = 0（未处理任何事件时成本为0，对应初始的空数组段）
• 状态转移：

  dp[i] = min( dp[j] + distance( get_last_segment(j), arr[j:i] ) )  其中 j 的取值范围是 max(0, i-L) ≤ j < i
  

  这里的L是你根据吉他物理特性设定的单段最大长度，比如单指法最多覆盖8个连续音符、时间跨度不超过4秒等，加这个限制后可以直接把状态转移的复杂度压到可控范围。
• 结果回溯：计算完dp[n]（n是总事件数）后，从n倒序查prev数组就能得到所有分割点。

2. 最短路径映射解法 #

你也可以把问题直接转化为正权图的最短路径问题，实现更简单：

• 每个节点对应「处理到第i个事件」的状态，节点编号从0到n
• 对于每个节点i，生成所有合法的出边：从i到j（j>i，且arr[i:j]符合单指法段的要求），边的权重为从i位置之前的最后一个段切换到arr[i:j]的难度
• 所有边权重都是正数（切换难度不可能为负），直接用Dijkstra算法求从0到n的最短路径，路径上的节点就是你要的分割索引。

3. 优化建议 #

• 提前预计算所有合法段的指法模式和切换难度，避免重复计算
• 如果需要考虑同一组音符对应多种可选指法的情况，可以把状态扩展为dp[i][s]，其中s是当前段对应的指法模式，吉他的指法模式总数有限（最多几千种），不会带来过大的性能开销
• 对于长度超过10分钟的长MIDI，可以按段落（比如按乐段分隔、静音分隔）先做粗分割，再对每个子段落单独求解，进一步提升效率。

内容的提问来源于stack exchange，提问作者porras