数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找执行乘法运算后的最大得分
假设我们有两个数组 nums 和 multipliers，大小分别为 n 和 m（n >= m）。数组从 1 开始索引。现在我们的初始得分为 0。我们想要执行正好 m 次操作。在第 i 次操作（从 1 开始索引）中，我们将：
从 nums 的开头或结尾选择一个值 x。
将 multipliers[i] * x 加到得分中。
从数组 nums 中移除 x。
我们必须找到执行 m 次操作后的最大得分。
因此，如果输入类似于 nums = [5,10,15]，multipliers = [5,3,2]，则输出将为 115，因为我们可以取 15 然后将其乘以 5 得到 5*15 = 75，然后 10*3 = 30，所以总计为 75+30 = 105，最后 5*2 = 10，所以总计 105+10 = 115。
为了解决这个问题，我们将遵循以下步骤：
n := nums 的大小，m := multipliers 的大小
dp := 一个大小为 m x (m+1) 的二维数组，并填充为 0
对于 i 反向遍历范围 0 到 m - 1，执行：
对于 j 遍历范围 i 到 m - 1，执行：
k := i + m - j - 1
dp[i, j] = (nums[i] * multipliers[k] + dp[i+1, j]) 和 (nums[j-m+n] * multipliers[k] + dp[i, j-1]) 的最大值
返回 dp[0] 的最后一个元素
示例
让我们看看以下实现以获得更好的理解：
def solve(nums, multipliers):
n, m = len(nums), len(multipliers)
dp = [[0]*m for _ in range(m+1)]
for i in reversed(range(m)):
for j in range(i, m):
k = i + m - j - 1
dp[i][j] = max(nums[i] * multipliers[k] + dp[i+1][j], nums[j-m+n] * multipliers[k] + dp[i][j-1])
return dp[0][-1]
nums = [5,10,15]
multipliers = [5,3,2]
print(solve(nums, multipliers))输入
[5,10,15], [5,3,2]
输出
115
更新于: 2021年10月6日
258 次查看
广告