ДП по подмножествам (bitmask): почему рекурсия с мемоизацией ловит MLE/TLE и как перейти к итерации?

Проблема не в числе состояний, а в map: каждый доступ — O(log) с аллокацией узлов и дикой константой; на 5 млн состояний это сотни млн тяжёлых операций → TLE, плюс узлы дерева жрут память → MLE. Решение: плоский массив dp[1<<n][n] и итерация по маскам в порядке возрастания (подмаска всегда меньше надмаски как число).

const int INF = 1e9;
vector<vector<int>> dp(1 << n, vector<int>(n, INF));
dp[1][0] = 0;                         // старт в городе 0
for (int mask = 1; mask < (1 << n); mask++)
  for (int last = 0; last < n; last++) {
    if (dp[mask][last] == INF || !(mask & (1 << last))) continue;
    for (int nxt = 0; nxt < n; nxt++) {
        if (mask & (1 << nxt)) continue;
        int nm = mask | (1 << nxt);
        dp[nm][nxt] = min(dp[nm][nxt], dp[mask][last] + cost[last][nxt]);
    }
  }
int ans = INF;
for (int last = 1; last < n; last++)
    ans = min(ans, dp[(1<<n)-1][last] + cost[last][0]);

Сложность O(2^n · n²) время, O(2^n · n) память. Для n=18: 2^18·18 ≈ 4.7M int ≈ 19 МБ — влезает. Грабля: проверяй mask & (1<<last) (этот город уже посещён) перед использованием состояния, иначе считаешь из недостижимых состояний.