สมมติว่าเรามีสองอาร์เรย์ nums และตัวคูณของขนาด n และ m ตามลำดับ (n>=m) อาร์เรย์มี 1 ดัชนี ตอนนี้คะแนนเริ่มต้นของเราคือ 0 เราต้องการดำเนินการ m ให้ถูกต้อง ในการดำเนินการ ith (จัดทำดัชนี 1 รายการ) เราจะ -
-
เลือกค่าหนึ่งค่าจาก x จากจุดเริ่มต้นหรือจุดสิ้นสุดของตัวเลข
-
เพิ่มตัวคูณ[i] * x ให้กับคะแนน
-
ลบ x ออกจากจำนวนอาร์เรย์
เราต้องหาคะแนนสูงสุดหลังจากดำเนินการ m แล้ว
ดังนั้น หากอินพุตเท่ากับ nums =[5,10,15] ตัวคูณ =[5,3,2] ผลลัพธ์จะเป็น 115 เพราะเราสามารถนำ 15 มาคูณกับ 5 ได้ 5*15 =75 จากนั้น 10*3 =30 ดังนั้นยอดรวมคือ 75+30 =105 และสุดท้าย 5*2 =10 ดังนั้นรวม 105+10 =115
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของ nums, m :=ตัวคูณขนาด
-
dp :=หนึ่งอาร์เรย์ 2 มิติขนาด m x (m+1) และเติมด้วย 0
-
สำหรับฉันกลับรายการช่วง 0 ถึง m - 1 ทำ
-
สำหรับ j ในช่วง i ถึง m - 1 ทำ
-
k :=i + m - j - 1
-
dp[i, j] =สูงสุดของ (nums[i] * ตัวคูณ[k] + dp[i+1, j]) และ (nums[j-m+n] * ตัวคูณ[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
