Chương trình tìm điểm tối đa từ phép nhân trong Python

Cho mảng nums (size n) và multipliers (size m), n ≥ m. Điểm ban đầu 0. Thực hiện m phép: chọn x từ đầu hoặc cuối nums, cộng multipliers[i] * x, xóa x. Tìm điểm tối đa.

Ví dụ: nums = [5,10,15], multipliers = [5,3,2], đầu ra = 115 (chọn 15*5 + 10*3 + 5*2 = 75+30+10).

Giải pháp

DP bottom-up: dp[i][j] = điểm tối đa khi đã chọn i phần tử từ trái, j từ phải (i+j = bước hiện tại):

• n := len(nums), m := len(multipliers)
• dp := ma trận (m+1) x m điền 0
• Với i từ m-1 xuống 0:
  • Với j từ i đến m-1:
    • k := i + m - j - 1 (index multiplier)
    • dp[i][j] = max(nums[i]*multipliers[k] + dp[i+1][j], nums[j-m+n]*multipliers[k] + dp[i][j-1])
• Trả về dp[0][-1]

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

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))

Đầu vào

[5,10,15], [5,3,2]

Đầu ra

115