给定一个长度为 n 的正整数数组 coins，每个元素表示对应位置的金币数量。 取位置 的金币时，假设左边一堆金币数量是，右边一堆金币数量为，则获得的积分。如果左边或右边没有金币，则金币数量视为1。 请你计算最多能得到多少积分。 数据范围：数组长度满足 ，数组中的元素满足
区块链毕设网qklbishe.com为您提供问题的解答
给定一个长度为 n 的正整数数组 coins，每个元素表示对应位置的金币数量。
取位置 
的金币时，假设左边一堆金币数量是
，右边一堆金币数量为
，则获得
的积分。如果左边或右边没有金币，则金币数量视为1。
请你计算最多能得到多少积分。
数据范围：数组长度满足 
，数组中的元素满足 
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param coins int整型一维数组 # @return int整型 # class Solution: """ 题目： https://www.nowcoder.com/practice/cb33f5653a064b2eaf1fe30ba18f5977?tpId=196&tqId=40524&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 参考： 大神：牛客202157047号 算法： 题目说明：如果左边或右边没有金币，则金币数量视为1。为了方便计算，我们对coins数组进行扩展，在左右两侧各加一个1，得到tmpCoins。 [5, 6, 4, 8] ==> [1, 5, 6, 4, 8, 1] 设dp[i][j]表示从下标i~下标j的区间，所能获得的最大积分 状态转移方程： dp[i][i] = coins[i - 1] * coins[i] * coins[i + 1] 对于区间[i, j]: 边界考虑： 1）最后选取的数是左边界，即最后选取的是coins[i] dp[i][j] = dp[i + 1][j] + coins[i - 1] * coins[i] * coins[j + 1] 2）最后选取的数是右边界，即最后选取的coins[j] dp[i][j] = dp[i][j - 1] + coins[i - 1] * coins[j] * coins[j + 1] 最后选取的数是k，i < k < j dp[i][j] = max(dp[i][j], dp[i][k - 1] + coins[i - 1] * coins[k] * coins[j + 1] + dp[k + 1][j]) 复杂度： 时间复杂度：O(n^3) 空间复杂度：O(n^2) """ def getCoins(self , coins): n = len(coins) coins = [1] + coins + [1] dp = [[0] * (n + 2) for _ in range(n + 2)] for i in range(1, n + 1): dp[i][i] = coins[i - 1] * coins[i] * coins[i + 1] for i in range(n, 0, -1): for j in range(i + 1, n + 1): left = dp[i + 1][j] + coins[i - 1] * coins[i] * coins[j + 1] # 最后选取的是coins[i] right = dp[i][j - 1] + coins[i - 1] * coins[j] * coins[j + 1] # 最后选取的是coins[j] dp[i][j] = max(left, right) for k in range(i + 1, j): # 最后选取的是coins[k] dp[i][j] = max(dp[i][j], dp[i][k - 1] + coins[i - 1] * coins[k] * coins[j + 1] + dp[k + 1][j]) # print dp return dp[1][n] if __name__ == "__main__": sol = Solution() coins = [5, 6, 4, 8] res = sol.getCoins(coins) print res
20:42
以上就是关于问题给定一个长度为 n 的正整数数组 coins，每个元素表示对应位置的金币数量。 取位置 的金币时，假设左边一堆金币数量是，右边一堆金币数量为，则获得的积分。如果左边或右边没有金币，则金币数量视为1。 请你计算最多能得到多少积分。
数据范围：数组长度满足 ，数组中的元素满足的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}