【动态规划】
Problem Link
给出整数数组 A
,将该数组分隔为长度最多为 K 的几个(连续)子数组。分隔完成后,每个子数组的中的值都会变为该子数组中的最大值。
返回给定数组完成分隔后的最大和。
Example:
示例:
输入:A = [1,15,7,9,2,5,10], K = 3
输出:84
解释:A 变为 [15,15,15,9,10,10,10]
提示:
1 <= K <= A.length <= 500
0 <= A[i] <= 10^6
Analysis
具体每一段的分割长度未知,属于典型的动态规划问题。若考虑是否以当前位置的数字作为该段中的最大值,但难以保证这一段数组的区间。
具体思路如下:
定义 dp[i]
为子数组 A[0, i]
按照题意分割后的最大和(最优解)
定义最后一个分割区间长度 j
, 则显然 $j ∈ [1, K]$
定义最后一个分割区间最大值 domainMax
, 则有 $domainMax = max{A[i-j+1, i]}$
对于每种取值,均可更新最优解,因此转移公式为:
$$\begin{equation}dp[i]=\left{\begin{array}{lr}\text{dp[i],}&\quad\text{当前分割区间长度 j 不是最优解,}\text{dp[i-j] + j*domainMax,} &\quad\text{当前分割区间长度 j 是最优解.}\end{array}\right.\end{equation} $$
边界条件为 i < K
, 即必须满足 i - j >= 0
。
Solution 【动态规划】
执行用时 : 14 ms, 在Partition Array for Maximum Sum的Java提交中击败了88.89% 的用户
内存消耗 : 36 MB, 在Partition Array for Maximum Sum的Java提交中击败了100.00% 的用户
|
|
复杂度分析
时间:$O(N*K)$
空间:$O(N)$
Notes
动态规划问题步骤
- 寻找最优解的表示
- 状态转移方程
- 边界条件判断