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

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

[]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
    }
}

1770. 执行乘法运算的最大分数 - Kotlin 多维DP到一维DP

常规思路

复杂度

Code

滚动数组优化

思路

复杂度

Code