Memoization doesn't seem to work here [IOI '00 P1 — Palindrome] on DMOJ.

Revision en1, by CodeRazer, 2023-03-11 15:05:11

Problem: https://dmoj.ca/problem/ioi00p1

I have written the following code for this problem (got the same problem accepted on leetcode with the same code).

#include <iostream>
#include <iomanip>
#include <array>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <climits>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#define ll long long
#define ull unsigned long long
const int MOD = (int)1e9 + 7;

using namespace std;

int dp[5000][5000];

int solve(int left, int right, string& s) {
    if (dp[left][right] != -1) {
        return dp[left][right];
    }
    if (left >= right) {
        return 0;
    }
    if (s[left] != s[right]) {
        dp[left][right] = min(1 + solve(left, right - 1, s), 1 + solve(left + 1, right, s));
    } else {
        dp[left][right] = solve(left + 1, right - 1, s);
    }
    return dp[left][right];
}

int main() {
    int n; cin >> n;
    string s; cin >> s;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = -1;
        }
    }
    cout << solve(0, n - 1, s) << '\n';
}

This gives RTE (segmentation fault) for some reason. I don't understand what I'm doing wrong.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English CodeRazer 2023-03-11 15:05:11 1375 Initial revision (published)