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 be the least cost to turn into palindrome. Obviously we have . As to turn to palindrome string, we can at first turn to palindrome and if then we need not do anything to make to palindrome, or we have to modify the string which have several possible cases:

  1. We can first make to palindrome and add after or remove
  2. We can first make to palindrome and add before or remove

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:

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;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(;
        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);