BOJ-10942パリンドロン?

これは,与えられた数列,与えられた始点と終点の間の数列がパリンドロンであるか否かを判断する問題である.
解題ポリシー
まず,ファリンドロンは中間数を基準とした対称数列を意味する.
1 2 3 2 1のような場合をパリン症候群といいます.
法林症候群かどうかを判断する方法は基本的にO(n)の時間的複雑さで求めることができる.
しかし、ファリム症候群かどうかを判断するには、最大10万個のO(n)を使用し、最悪の場合は10万個のx 2000を使用するため、タイムアウトとなる.
従って,O(n)法で解くのは不合理である.
ファリンドロンの特徴は、両端点を除いて中間部分がファリンドロンを維持していることです.
上記の例に示すように、1 2 3 2の場合、両端点以外の2 3 2もファリントロームを保持する.
すなわち、与えられた始点sと終点eが等しい場合、s+1~e−1がパリンドロンであれば、s~eもパリンドロンであると判断できる.
この過程はdpで解くことができる.
コード#コード#

#include<iostream>
#include<vector>

using namespace std;

int n;
int m;
vector<int> v;
int dp[2001][2001];
int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> n;
    v.push_back(-1);
    for(int i=1;i<=n;i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
        dp[i][i] = 1;
    }

    for(int i=1;i<n;i++){ // 파악 갯수
        for(int j=1;j<=n-i;j++){ // 각 경우
            if(v[j] == v[j+i]){
                if(i == 1 || dp[j+1][j+i-1] == 1) // 길이가 2 이거나 j+1,j+i-1일때 팰린드롬이면
                    dp[j][j+i] = 1;
            }
        }
    }

    cin >> m;
    for(int i=0;i<m;i++){
        int s,e;
        cin >> s >> e;
        cout << dp[s][e] << "\n";
    }
}

ソース
https://www.acmicpc.net/problem/10942
振り返る
1つ目のアイデアは,2反復文を単純にi=1~n−1/j=i+1~nに変換することであり,この方式を用いると,条件節のdp[i+1][j−1]の値が設定されていないため,誤った答えが得られる.
だから繰り返し文を所定の数の部分と各場所に回した.