POJ. 3280 Cheapest Palindrome

1.Problem
http://poj.org/problem?id=3280

2.Idea
DP[l][r]: the best cost of substring that starts l and ends r. Then the following interval dp is true.
dp[l][r] = dp[l+1][r -1], if s[l] == s[r]
dp[l][r] = min(dp[l+1][r] + cost[s[l]], dp[l][r-1] + cost[s[r]]), if s[l] != s[r]

3.Source

 int n, m;  
 string s;  
 map<char, int> Cost;  
 int dp[2003][2003];  
 int main()  
 {  
      cin >> n >> m;  
      cin >> s;  
      char c;  
      int l, r;  
      for (int i = 0; i < n; i++) {  
           cin >> c >> l >> r;  
           Cost.insert(make_pair(c, min(l, r)));  
      }  
      for (int len = 1; len < m; len++) {  
           for (int i = 0, j = len; j < m; i++, j++) {  
                if (s[i] == s[j]) {  
                     dp[i][j] = dp[i + 1][j - 1];  
                }  
                else {  
                     dp[i][j] = min(dp[i + 1][j] + Cost[s[i]], dp[i][j - 1] + Cost[s[j]]);  
                }  
           }  
      }  
      cout << dp[0][m-1] << endl;  
       return 0;  
 }