class Solution
{
public:
   string s;
int n;
unordered_map<string, bool> exist;
int dp[2222];
int rec(int at) {
    if(at >= s.size()) {
        return 1;
    }
    if(dp[at] != -1) {
        return dp[at];
    }
    int res = 0;
    string tmp = "";
    for(int i = at; i < s.size(); i++) {
        tmp += s[i];
        if(exist[tmp]) {
            res = max(res, rec(at + tmp.size()));
        }
    }
    return dp[at] = res;
}
int wordBreak(int n, string s, vector<string> &dictionary) {
        this->n = n;
        this->s = s;
        for(string s : dictionary) {
            exist[s] = true;
        }
        memset(dp, -1, sizeof dp);
        return rec(0);
}
};