โปรแกรมหาคะแนนบวกสูงสุดจากการลบตัวเลขใน Python

สมมติว่ามีรายการตัวเลข nums ดำเนินการเลือกตัวเลข (ไม่ใช่ตัวแรกหรือตัวสุดท้าย) ลบออก และเพิ่มคะแนนเท่ากับผลรวมของตัวเลขนั้นและสองตัวข้างเคียง ทำได้หลายครั้ง ต้องการคะแนนสูงสุด

ตัวอย่าง: nums = [2, 3, 4, 5, 6] ผลลัพธ์คือ 39 เลือก 5 ได้ 15, เลือก 4 ได้ 13, เลือก 3 ได้ 11 รวม 39

ขั้นตอนการแก้ปัญหา

1. n = len(nums), ถ้า n < 3 คืน 0
2. สร้าง DP 2D ขนาด (n+1) x (n+1)
3. วน len จาก 3 ถึง n:
   • วน i จาก 1 ถึง n-len+1:
     • r = i + len - 1
     • หา k ที่ให้คะแนนมากที่สุด: dp[i][k] + dp[k][r] + nums[k-1]
     • dp[i][r] = max_score + nums[i-1] + nums[r-1]
4. คืน dp[1][n]

ตัวอย่างโค้ด

class Solution:
    def solve(self, nums):
        n = len(nums)
        if n < 3:
            return 0
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for length in range(3, n + 1):
            for i in range(1, n - length + 2):
                r = i + length - 1
                ans = 0
                for k in range(i + 1, r):
                    curr = dp[i][k] + dp[k][r] + nums[k - 1]
                    if curr > ans:
                        ans = curr
                ans += nums[i - 1] + nums[r - 1]
                dp[i][r] = ans
        return dp[1][n]

ob = Solution()
nums = [2, 3, 4, 5, 6]
print(ob.solve(nums))

อินพุต

[2, 3, 4, 5, 6]

เอาต์พุต

39