Scriba — interval

Step 1 / 7

Bai toan Zuma: cho day bi mau "RBBRBR" (6 bi). Tim so buoc it nhat de xoa het. dp[l][r] = so buoc xoa doan [l..r].

Step 2 / 7

Co so: moi bi don le can 1 buoc de xoa. dp[i][i] = 1 voi moi i.

Step 3 / 7

dp[1][2]: "BB" – hai bi cung mau, xoa 1 lan. dp[1][2] = 1.

Step 4 / 7

Cac doan dai 2 khac mau: dp[0][1]=2 (RB), dp[2][3]=2 (BR), dp[3][4]=2 (RB), dp[4][5]=2 (BR).

Step 5 / 7

Doan dai 3: dp[0][2]=2 (R ghep BB), dp[1][3]=2 (BBR, xoa BB roi R), dp[2][4]=2 (BRB), dp[3][5]=2 (RBR, R hai dau ghep).

Step 6 / 7

Tinh dp[2][5] cho doan "BRBR". Xet tat ca cach chia va ghep bi cung mau.

Chia tai k=3: dp[2][3] + dp[4][5] = 2 + 2 = 4. Hoac ghep a[2]=B voi a[4]=B: dp[3][3] + dp[2][4 voi B ghep] = 1 + 1 = 2.

dp[2][5] = 2. Ghep hai bi B o vi tri 2 va 4, xoa R o giua, roi xoa cap BB.

Step 7 / 7

dp[0][5] = 2: toan bo day "RBBRBR" chi can 2 buoc. Ghep R dau va R cuoi, xoa BB giua, roi xoa RR. Ket qua toi uu!

interval_dp