Potions

• Time : $O(n^3)$
• Space : $O(n^2)$

pair<int, int> helper(int i, int j, vector<int> &A, vector<vector<pair<int,int>>> &dp){
    pair<int, int>& res = dp[i][j];
    if(dp[i][j].first != -1) return res;
    if(i == j) return res = {0,A[i]};
    if(j == i + 1) res = {A[i] * A[j], (A[i] + A[j]) % 100};

    res = {INT_MAX, INT_MAX};
    for(int k = i + 1; k <= j; k++) {
        auto l = helper(i,k-1,A,dp);
        auto r = helper(k,j,A,dp);
        
        pair<int,int> now = {l.first + r.first + l.second * r.second, (l.second + r.second) % 100};
        if(now.first < res.first) res = now;
    }
    return res;
}

int Solution::minSmoke(vector<int> &A) {
    if(A.size() == 1) return 0;
    if(A.size() == 2) return A[0] * A[1];
    vector<vector<pair<int,int>>> dp(A.size(), vector<pair<int,int>>(A.size(), {-1, -1}));
    return helper(0,A.size() - 1, A, dp).first;
}