โจทย์: หา subsequence แพลินโดรม (palindromic subsequence) ที่มีความยาวเป็นเลขคู่ และไม่มีตัวอักษรซ้ำติดกันยกเว้นตรงกลาง ใช้ Dynamic Programming เก็บคู่ (ความยาว, ตัวอักษรสุดท้าย) ในตาราง 2 มิติ
อัลกอริทึม
- สร้างตาราง dp[n][n] เก็บ tuple (length, last_char) เริ่มต้น (0, '')
- วน i จาก n-1 ถึง 0, j จาก i+1 ถึง n-1
- ถ้า s[i] == s[j] และ dp[i+1][j-1][1] != s[i]: dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
- ไม่เช่นนั้น: dp[i][j] = max ของ dp[i+1][j], dp[i][j-1], dp[i+1][j-1] ตามความยาว
- คืนค่า dp[0][n-1][0]
ตัวอย่างโค้ด
def solve(s):
n = len(s)
dp = [[(0, '')] * n for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if s[i] == s[j] and dp[i+1][j-1][1] != s[i]:
dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0])
return dp[0][n-1][0]
print(solve('efeffe')) # Output: 4
อินพุต/เอาต์พุต
Input: 'efeffe' Output: 4
คำอธิบาย: subsequence แพลินโดรมคู่ที่ยาวที่สุดคือ 'effe' ความยาว 4
