[백준 10942] 팰린드롬 ? (DP) (C/C++) (★★)

1.

#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
 
int N, M;
int arr[2010];
int dp[2010][2010]; // [시작][끝] 
 
int solve(int s, int e)
{
    if(s >= e)
    {
        return 1;
    }
    
    if(dp[s][e] != -1)
    {
        return dp[s][e];
    }
    
    dp[s][e] = 0;
    
    if(arr[s] == arr[e])
    {
        dp[s][e] = solve(s+1, e-1);    
    }
    
    return dp[s][e];
}
 
int main(void)
{
//    freopen("B10942_input.txt", "r", stdin);
    
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }
    memset(dp, -1, sizeof(dp));
    
    cin >> M;
    
    for(int i = 1; i <= M; i++)
    {
        int s, e;
        cin >> s >> e;
        
        cout << solve(s, e) << "\n";
    }
 
    return 0;
}

 

2.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int N, M;
int arr[2010];
int dp[2010][2010]; // [시작][끝] 
 
int main(void)
{
//    freopen("B10942_input.txt", "r", stdin);
    
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }
    
    // 길이 1
    for(int i = 1; i <= N; i++)
    {
        dp[i][i] = 1;    
    } 
    
    // 길이 2
    for(int i = 1; i <= N-1; i++)
    {
        if(arr[i] == arr[i+1])
        {
            dp[i][i+1] = 1;
        }    
    } 
    
    // 길이 3이상
    for(int k = 3; k <= N; k++)
    {
        for(int i = 1; i <= N-k+1; i++)
        {
            int j = i+k-1;
            
            if(arr[i] == arr[j] && dp[i+1][j-1] == 1)
            {
                dp[i][j] = 1;
            }
        }
    }
    
    cin >> M;
    
    for(int i = 1; i <= M; i++)
    {
        int s, e;
        cin >> s >> e;
        
        cout << dp[s][e] << "\n";
    }
 
    return 0;
}