Simple C++ DP solution


#1
vector<vector<vector<TreeNode*>>> dp(A + 2, vector<vector<TreeNode*>>(A + 2));

// handle base cases of l > r
for(int i = 0; i < A + 2; i++){
    for(int j = 0; j < i; j++){
        dp[i][j].push_back(NULL);
    }
}

// palindromic substring type DP
for(int len = 1; len <= A; len++){
    for(int l = 1; l + len - 1 <= A; l++){
        int r = l + len - 1;
        for(int root = l; root <= r; root++){
            
            for(auto &z: dp[l][root-1]){
                for(auto &q: dp[root+1][r]){
                    TreeNode* n = new TreeNode(root);
                    n->left = z;
                    n->right = q;
                    dp[l][r].push_back(n);
                }
            }
        }
    }
}

return dp[1][A];

#2

I thought an iterative version would pass the worst case of the given constraints but it doesn’t. I know this is nitpicking. Did you test it for A = 15?