Cheapest Palindrome (POJ 3280)

This is quite a problem of high quality. Given a piece of string, use are asked to return the minium cost to turn that string into a palindrome string. You can add or remove characters in a given set with different cost.

You actually need not find the final palindrome string first and then calculate the cost. That will be too hard. On contrary we use dynamic programming method to find the minimum cost direactly.

Let $DP[i][j]$ be the least cost to turn $s[i..j]$ into palindrome. Obviously we have $DP[i][i] = 0$. As to turn $s[i..j]$ to palindrome string, we can at first turn $s[i+1..j-1]$ to palindrome and if $s[i] = s[j]$ then we need not do anything to make $s[i..j]$ to palindrome, or we have to modify the string which have several possible cases:

1. We can first make $s[i+1..j]$ to palindrome and add $s[i]$ after $j$ or remove $s[i]$
2. We can first make $s[i..j-1]$ to palindrome and add $s[j]$ before $i$ or remove $s[j]$

In both cases we can either add a character or remove a character, to add or remove is up to which operation of corresponding character is cheaper. So the iteration formular will be:

$$DP[i][j]=\begin{cases} DP[i+1][j-1] & s[i]=s[j]\\ \max\left\{ DP[i+1][j]+cost(s[i]),DP[i][j-1]+cost(s[j])\right\} & otherwise \end{cases}$$

import java.io.*;
import java.util.*;

public class CheapestPalindrome {
    private static void solve(char[] str, Map<Character, Integer> cost) {
        int M = str.length;
        int[] dp = new int[M];
        int[] last = new int[M];
        for (int j = 1; j < M; j++) {
            for (int i = j - 1; i >= 0; i--) {
                if (str[i] == str[j]) {
                    dp[i] = last[i + 1];
                } else {
                    dp[i] = Math.min(dp[i + 1] + cost.get(str[i]), last[i] + cost.get(str[j]));
                }
            }
            int[] tmp = dp;
            dp = last;
            last = tmp;
        }
        System.out.println(last[0]);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] str;
        str = in.readLine().split(" ");
        int N = Integer.parseInt(str[0]), M = Integer.parseInt(str[1]);
        char[] chars = in.readLine().toCharArray();
        HashMap<Character, Integer> cost = new HashMap<Character, Integer>();
        for (int i = 0; i < N; i++) {
            str = in.readLine().split(" ");
            char c = str[0].charAt(0);
            int deletion = Integer.parseInt(str[1]), addition = Integer.parseInt(str[2]);
            cost.put(c, Math.min(deletion, addition));
        }
        solve(chars, cost);
    }
}