题目内容

在通信系统中，有一组数据包需要按顺序通过 $k$ 个通道传输。每个数据包 $i$ 的传输耗时为 $nums[i]$（单位：毫秒）。

传输规则

• 同一通道内的数据包必须按顺序连续传输，即若数据包 $[i,\ i+1,\ ...,\ j]$ 分配给同一通道，则该通道的传输总延迟为 $nums[i] + nums[i+1] + ... + nums[j]$。
• 不同通道之间可以并行传输，系统整体延迟取决于延迟最大的那个通道。
• 数据包只能被拆分为连续子段，例如 $[1,\ 2,\ 3]$ 可以被拆分为 $[1,\ 2],\ [3]$，但是不能被拆分为 $[1,\ 3],\ [2]$。

你的任务是：将 $nums$ 数组划分到 $k$ 个连续非空通道，使得传输总耗时最小。

输入描述

• $nums$：非负整数数组，长度 $n$（$1 \le n \le 1000$），每个元素满足 $0 \le nums[j] \le 10^6$。
• $k$：整数，通道数量（$1 \le k \le n$）。

输出描述

• 返回一个整数，值为符合题意的最优传输策略下的总耗时。

样例1

输入

[7, 2, 5, 10, 8],2

输出

18

说明

输入: $nums = [7,\ 2,\ 5,\ 10,\ 8],\ k = 2$ 输出: $18$ 解释: 共有以下划分方案（划分为$2$个连续子数组）： 方案1: $[7],\ [2,5,10,8] \to$ 总耗时为 $25$ 方案2: $[7,2],\ [5,10,8] \to$ 总耗时为 $23$ 方案3: $[7,2,5],\ [10,8] \to$ 总耗时为 $18 \leftarrow$ 最优 方案4: $[7,2,5,10],\ [8] \to$ 总耗时为 $24$ 因此最优总耗时为 $18$。

样例2

输入

[1, 2, 3, 4, 5],2

输出

9

说明

输入: $nums = [1,\ 2,\ 3,\ 4,\ 5],\ k = 2$ 输出: $9$ 解释: 最优划分为 $[1,2,3]$ 和 $[4,5]$，最优总耗时为 $9$。

样例3

输入

[1, 4, 4],3

输出

4

说明

输入: $nums = [1,\ 4,\ 4],\ k = 3$ 输出: $4$ 解释: 划分为 $[1],\ [4],\ [4]$，最优总耗时为 $4$。