Code : Finding the number of palindromes (Large)

#include <bits/stdc++.h>
using namespace std;

// Template starts
#include <codeforces/modint.hpp>
// Template ends

constexpr int md = (int)10007;
using mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

void solve(string &str) {
    int n = str.length();
    vector<vector<mint>> dp(n, vector<mint>(n, 0));
    // dp[i][j] is the number of non-empty palindromic subsequence of [i...j].

    // Fill all length 1 manually.
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (int i = n - 2; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            // You can always choose to delete one of the endpoints.
            // The case when both endpoints are eventually deleted are double
            // counted, hence we subtract it once.
            dp[i][j] += dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];

            // You can choose to keep both the endpoints only it they
            // are identical.
            if (str[i] == str[j]) {
                // You can either stop the process right here and walk away
                // with 2 elements str[i] and str[j], or you can ask for the
                // inner subsequence to be a non-empty palindrome.
                dp[i][j] += 1 + dp[i + 1][j - 1];
            }
        }
    }

    cout << dp[0][n - 1] << endl;
}

int main() {
    string str;
    cin >> str;
    solve(str);
    return 0;
}

// Why is dp[i][i] = 1 instead of 2?
//
// If we are not allowing empty subsequences for intermediate values,
// how do account we for the subsequence `aa` created by `aba`, i.e, by
// deleting inner b and keeping the terminal a?

// Answer lies in the fact that we add `1` to dp[i][j] if the terminal
// elements are equal. The 1 indicates a way of stopping right there and
// taking the inner subsequence, making it empty.
//
// If you keep dp[i][i] = 2, a lot of things would be double counted,
// difficult to maintain.