ガチョウ工場2016実習生募集試験問題2

タイトルの要求:abefbcaのような文字列を与えて、その中のいくつかの文字を削除することによって(もちろん削除しなくてもいい)、あなたは最も長い1つの回文列の長さを見つけることができますか?abefbcaを例にして、私たちはcを削除することができて、efのある1つを削除することができて、回文列abebaを得て、あるいはabfba、それでは最も長い回文列は5です.
当時は書けなかったなんて、汗動的計画解を用いて,dp[i][j]はi番目の文字からj番目の文字までの最大返信長を表す.サブ問題に分解:1.最長回文はj番目の文字を含み、i番目の文字からj番目の文字と同じ状況に遭遇するまで後方検索を開始し、このときの文字の下にkと表記され、得られた値temp=2+dp[k+1][j-1]である.2.最長回文はj文字目を含まず、temp 2=dp[i][j-1].
ではdp[i][j]はtempとtemp 2の最大値をとる.

#include 
#include 
#include 
using namespace std;
int dp[1000][1000];
inline int max(int a, int b){
    return a > b ? a : b;
}
int main(){
    string s;
    cin >> s;
    int len = s.size();
    for (int i = 0; i < len; i++){
        dp[i][i] = 1;
    }
    for (int i = len - 1; i >= 0; i--){
        for (int j = 0; j < len; j++){
            if (i>j)
                continue;
            int temp = 1;
            for (int k = i; k < j; k++){
                if (s[k] == s[j]){
                    temp = 2 + dp[k + 1][j - 1];
                }
            }//temp      s[j]   
            int temp2 = dp[i][j - 1];//temp2        
            dp[i][j] = max(temp, temp2);
        }
    }
    cout << dp[0][s.size() - 1] << endl;
    return 0;
}