ขั้นตอนขั้นต่ำในการลบสตริงหลังจากลบสตริงย่อย palindrome ซ้ำๆ ใน C++

คำชี้แจงปัญหา

กำหนดสตริงที่มีอักขระเป็นจำนวนเต็มเท่านั้น เราจำเป็นต้องลบอักขระทั้งหมดของสตริงนี้ในจำนวนขั้นตอนขั้นต่ำ โดยในขั้นตอนเดียว เราสามารถลบสตริงย่อยซึ่งเป็นพาลินโดรมได้ หลังจากลบสตริงย่อยส่วนที่เหลือจะถูกต่อเข้าด้วยกัน

ตัวอย่าง

หากสตริงอินพุตคือ 3441213 จำเป็นต้องมีขั้นต่ำ 2 ขั้นตอน

ขั้นแรกให้ลบ 121 ออกจากสตริง ตอนนี้สตริงที่เหลือคือ 3443
ลบสตริงที่เหลือเนื่องจากเป็นพาลินโดรม

อัลกอริทึม

เราสามารถใช้โปรแกรมไดนามิกเพื่อแก้ปัญหานี้ได้

<ก่อน>1. ให้ dp[i][j] หมายถึงจำนวนขั้นตอนที่ใช้ในการลบสตริงย่อย s[i, j]2 อักขระแต่ละตัวจะถูกลบเพียงอย่างเดียวหรือเป็นส่วนหนึ่งของสตริงย่อย ดังนั้นในกรณีแรก เราจะลบอักขระนั้นเองและเรียกปัญหาย่อย (i+1, j)3 ในกรณีที่สอง เราจะวนซ้ำทุกการเกิดขึ้นของอักขระปัจจุบันทางด้านขวา ถ้า K เป็นดัชนีของเหตุการณ์ดังกล่าวหนึ่งรายการ ปัญหาจะลดลงเหลือสองปัญหาย่อย (i+1, K – 1) และ (K+1, จ)4. เราสามารถเข้าถึงปัญหาย่อยนี้ (i+1, K-1) เพราะเราสามารถลบอักขระเดียวกันและเรียกสตริงย่อยกลางได้5 เราจำเป็นต้องดูแลกรณีที่อักขระสองตัวแรกเหมือนกัน ในกรณีนี้ เราสามารถลดปัญหาย่อยได้โดยตรง (i+2, j)

ตัวอย่าง

#include ใช้เนมสเปซ std;int getMinRequiredSteps (สตริง str) { int n =str.length (); int dp[n + 1][n + 1]; สำหรับ (int i =0; i <=n; i++) { สำหรับ (int j =0; j <=n; j++) { dp[i][j] =0; } } for (int len =1; len <=n; len++) { สำหรับ (int i =0, j =len - 1; j  
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ดังต่อไปนี้
 ผลลัพธ์
 ขั้นตอนที่จำเป็นขั้นต่ำ:2