โปรแกรมหาคะแนนสูงสุดจากการดำเนินการคูณใน Python

สมมติว่าเรามีอาร์เรย์สองอาร์เรย์ nums และ multipliers ขนาด n และ m ตามลำดับ (n >= m) อาร์เรย์เป็น 1-indexed คะแนนเริ่มต้นคือ 0 เราต้องการดำเนินการ m ครั้งพอดี ในการดำเนินการครั้งที่ i (1-indexed) เราจะ:

• เลือกค่า x หนึ่งค่าจากต้นหรือปลายของ nums
• บวก multipliers[i] * x เข้ากับคะแนน
• ลบ x ออกจากอาร์เรย์ nums

เราต้องหาคะแนนสูงสุดหลังจากดำเนินการ m ครั้ง

เช่น ถ้าอินพุตคือ nums = [5,10,15], multipliers = [5,3,2] ผลลัพธ์จะเป็น 115 เพราะเราสามารถเอา 15 คูณ 5 ได้ 75 แล้ว 10*3 = 30 รวม 105 และสุดท้าย 5*2 = 10 รวม 115

วิธีแก้ปัญหา

• n := ขนาดของ nums, m := ขนาดของ multipliers
• dp := อาร์เรย์ 2D ขนาด m x (m+1) เติม 0
• สำหรับ i ในรายการช่วง 0 ถึง m - 1 เรียงย้อนกลับ:
  • สำหรับ j ในช่วง i ถึง m - 1:
    • 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]

ตัวอย่าง

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