1770. 执行乘法运算的最大分数 - Kotlin 多维DP到一维DP
Problem: 1770. 执行乘法运算的最大分数
常规思路 设dp[start][end]
是数组当前剩余元素为子数组nums[start...(end-1)]
时能够得到的最大分数,即左闭右开区间。这样做是考虑到存在拿到最后无剩余元素的情况 (如样例1)
如果对应nums[start...end]
,那么dp[0][0]
对应的是剩余元素仅有nums[0]
的情况而非无剩余元素的情况,对于无剩余元素的特判会较为麻烦(会出现形如dp[0][-1]
的索引)。类似的思路可以参考字符串的substring
函数
接下来考虑算法思路,对于普遍情况下的dp[start][end]
,也就是剩余子数组为nums[start...(end-1)]
的情况
剩余子数组的长度len=end-start
已知整个数组的长度为nums.size
那么当前已经选走的元素个数为nums.size-len
对于长度为 的剩余子数组,我们知道它是由一个长度为 的子数组拿走一个元素,分数加上该元素乘以mutipliers[nums.size-len-1]
重点在于最后一句,即长度为len
的子数组的解,是由长度为 的子数组得到的,因此最外层循环应当是len
遍历[nums.size-1,nums.size-mutipliers.size]
len=nums.size
时即数组尚未拿取任何元素,得分为0,因此直接初始化为0即可,此时对应唯一索引dp[0][nums.size]
len=nums.size-mutipliers.size
时即刚好拿取m个元素,此时拿取个数已满足需求,在最后一层循环中寻找最大值即为解
对于nums[start...(end-1)]
,它可能是nums[(start-1)...(end-1)]
拿走nums[start-1]
得到的,也可能是nums[start...end]
拿走nums[end]
得到的,对于这两种情况我们取较大值即为dp[start][end]
的解,即
复杂度
Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { fun maximumScore (nums: IntArray , multipliers: IntArray ) : Int { val dp = Array(nums.size) { IntArray(nums.size+1 ) { 0 } } var max=Int .MIN_VALUE for (length in nums.size-1 downTo nums.size-multipliers.size){ for (start in nums.indices){ val end = start+length if (end>nums.size){ break } dp[start][end]=Math.max( if (start-1 >=0 )dp[start-1 ][end]+nums[start-1 ]*multipliers[nums.size-length-1 ] else Int .MIN_VALUE, if (end<nums.size) dp[start][end+1 ]+nums[end]*multipliers[nums.size-length-1 ] else Int .MIN_VALUE ) if (length==nums.size-multipliers.size){ max=Math.max(max,dp[start][end]) } } } return max } }
滚动数组优化 思路 上述做法会开出一个 的数组,在较大的数据范围下会导致MLE,观察状态方程能够发现长度为len
的子数组只与长度为len+1
的子数组有关,因此我们可以将dp数组压缩为 的复杂度
设dp[len][start]
的剩余子数组以nums[start]
起始,子数组长度为len
的话,那么有:
我们只需要开一个dp[2][nums.size]
的数组,其中一行记录len
的解,一行记录len+1
的解,每次遍历完一次len(len–)后两行互换即可
复杂度
Code [] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { fun maximumScore (nums: IntArray , multipliers: IntArray ) : Int { val dp = Array(2 ) { IntArray(nums.size) { 0 } } var max = Int .MIN_VALUE var now = 0 var last= 1 for (length in nums.size - 1 downTo nums.size - multipliers.size) { for (start in nums.indices) { val end = start + length if (end > nums.size) { break } dp[now][start] = Math.max( if (start - 1 >= 0 ) dp[last][start - 1 ] + nums[start - 1 ] * multipliers[nums.size - length - 1 ] else Int .MIN_VALUE, if (end < nums.size) dp[last][start] + nums[end] * multipliers[nums.size - length - 1 ] else Int .MIN_VALUE ) if (length == nums.size - multipliers.size) { max = Math.max(max, dp[now][start]) } } if (now==0 ){ now=1 last=0 }else { now=0 last=1 } } return max } }