Оптимизировать означает изменить программу так что бы она тратила меньше ресурсов на вычисление результата. В вашем случае надо искать способ решить задачу быстрее.

Текущее решение делает много лишней работы. Перебираются и проверяются все числа. Это не нужно. Например, если число имеет вид 132xxxxxxx, то его и всех его соседей можно пропустить. Они точно не пройдут проверку.

Короткая дорога подсказана Harry в комментарии к вопросу. Видите числовую последовательность? Отыщите её в энциклопедии OEIS: https://oeis.org/search?q=1+10+100+475+1675+4954+12952. Точного совпадения не будет, но будет ссылка на последовательность без единицы в начале: A364342. Читаем статью, убеждаемся что это наша последовательность, находим формулу, программируем, готово.

Рекурсивное решение

Если не повезло и последовательность не нашлась, придётся решать задачу головой. Будем считать отдельно возрастающие и отдельно убывающие числа.

Возрастающие числа

Нужен опыт чтобы догадаться до a_n,d - количество возрастающих чисел из ровно n цифр и первая цифра не меньше d. Факты:

• a_n,9 = 1 – только одно возрастающее число из n цифр начинается с девятки;
• a_1,d = 10 - d – количество возрастающих чисел из одной цифры легко сосчитать;
• a_n,d = a_n,d+1 + a_n-1,d – это важная формула. Если число начинается с цифры строго больше d, то такие числа "считает" первое слагаемое. Если число начинается с цифры равной d, то такие числа "считает" второе слагаемое. В этой формуле n > 1 и d < 9.

Нас интересуют все возрастающие числа из не более чем n цифр. Обозначим их через a_n. Обратите внимание на один индекс.

a_n = 1 + Σ_1≤j≤n a_j,1 – надо сложить возрастающие числа всех подходящих длин и добавить единицу для нуля.

Код прямо повторяет формулы:

unsigned long long a(unsigned n, unsigned d) {
    if (d == 9) {
        return 1;
    }
    if (n == 1) {
        return 10 - d;
    }
    return a(n, d + 1) + a(n - 1, d);
}

unsigned long long a(unsigned n) {
    unsigned long long s = 1;
    for (unsigned j = 1; j <= n; ++j) {
        s += a(j, 1);
    }
    return s;
}

Убывающие числа

Схема та же: b_n,d - количество убывающих цепочек цифр (не чисел - здесь это важно) из ровно n цифр и первая цифра не больше d.

• b_n,0 = 1 – только одна убывающая цепочка из n цифр начинается с нуля;
• b_1,d = d + 1 – количество убывающих цепочек из одной цифры легко сосчитать;
• b_n,d = b_n,d-1 + b_n-1,d – если число начинается с цифры строго меньше d, то такие числа "считает" первое слагаемое. Если число начинается с цифры равной d, то такие числа "считает" второе слагаемое. В этой формуле n > 1 и d > 0.

Нас интересуют все убывающие числа (на этот раз не цепочки, числа) из не более чем n цифр. Обозначим их через b_n. Снова обратите внимание на один индекс.

b_n = (Σ_1≤j≤n b_j,9) - (n - 1) – надо сложить возрастающие цепочки всех подходящих длин и вычесть цепочки, которые не являются числами. Таких цепочек n - 1: 00, 000, 0000, ...

unsigned long long b(unsigned n, unsigned d) {
    if (d == 0) {
        return 1;
    }
    if (n == 1) {
        return d + 1;
    }
    return b(n, d - 1) + b(n - 1, d);
}

unsigned long long b(unsigned n) {
    unsigned long long s = 0;
    for (unsigned j = 1; j <= n; ++j) {
        s += b(j, 9);
    }
    return s - (n - 1);
}

"Монотонные" числа

Количество "монотонных" чисел c_n:

• c₀ = 1 – последовательности a и b не определены для n = 0, требуется отдельное определение;

• с_n = a_n + b_n - 9·n - 1 – число "монотонных" чисел это число возрастающих чисел плюс число убывающих чисел минус те числа, которые мы сосчитали два раза. Два раза сосчитан ноль и числа в которых все цифры одинаковы: 333, 9999. Таких чисел 9·n.

unsigned long long c(unsigned n) {
    if (n == 0) {
        return 1;
    }
    return a(n) + b(n) - 9 * n - 1;
}

Динамическое программирование

Это решение на моём железе считает c₂₅ = 236030401 за одну секунду. Это лучше чем было, но можно ещё лучше. Функции a(n, d) и b(n, d) многократно вызываются для одних и тех же аргументов. Заменим их на таблицы:

unsigned long long a(unsigned n) {
    std::vector<std::array<unsigned long long, 10>> a(n + 1);
    for (unsigned i = 1; i < 10; ++i) {
        a[1][i] = 10 - i;
    }
    for (unsigned j = 2; j <= n; ++j) {
        a[j][9] = 1;
        for (unsigned i = 8; i > 0; --i) {
            a[j][i] = a[j][i + 1] + a[j - 1][i];
        }
    }

    unsigned long long s = 1;
    for (unsigned j = 1; j <= n; ++j) {
        s += a[j][1];
    }
    return s;
}

unsigned long long b(unsigned n) {
    std::vector<std::array<unsigned long long, 10>> b(n + 1);
    for (unsigned i = 1; i < 10; ++i) {
        b[1][i] = i + 1;
    }
    for (unsigned j = 2; j <= n; ++j) {
        b[j][0] = 1;
        for (unsigned i = 1; i < 10; ++i) {
            b[j][i] = b[j][i - 1] + b[j - 1][i];
        }
    }

    unsigned long long s = 0;
    for (unsigned j = 1; j <= n; ++j) {
        s += b[j][9];
    }
    return s - (n - 1);
}

Этот код считает быстро и правильно для n ≤ 375. c₃₇₅ = 17980269677772943001. Дальше переполняется unsigned long long. Расчёт занимает микросекунды, можно было бы успокоится. Но есть способ быстрее и с меньшим количеством кода.

Сочетания

Возрастающие числа

Возьмём любое возрастающее число из не более чем n цифр, дополним его нулями слева до n цифр ровно. Обозначим d_i, 0 ≤ i ≤ 9 - количество цифр i в дополненой строке. Построим строку: d₀ звёздочек, палка, d₁ звёздочек, палка, ..., палка, d₉ звёздочек. В получившейся строке будет ровно n звёздочек и девять палочек.

Например n = 14 и число 12229999. Тогда d₀ = 6 – столько нулей нужно чтобы общая длина стала n. d₁ = 1, d₂ = 3, d₉ = 4. Остальные значения - нули. Строка из звёздочек и палочек: ******|*|***|||||||****.

Имеем отображение, которое любое возрастающее число < 10ⁿ переводит в строку из n звёздочек и девяти палочек. Разные числа переходят в разные строки.

Обратно, любая строка из n звёздочек и девяти палочек переводится в число. В первой группе звёздочки заменяет на нули, во второй на единицы и так далее. Палочки удаляем, ведущие нули удаляем, получается возрастающее число.

И снова любая строка из n звёздочек и девяти палочек переводится в возрастающее число < 10ⁿ. Разные строки переводятся в разные числа.

Тогда количество возрастающих чисел и количество строк из n звёздочек и девяти палочек одинаково. Сосчитаем количество строк. Сколькими способами можно расставить девять палочек на n + 9 мест? В статье Сочетание сказано что это число сочетаний из n + 9 по 9:

(ⁿ⁺⁹₉) = C_n+9⁹ = ^{(n + 9)!}/_(n!·9!)

Убывающие числа ...

... подсчитываются немного сложнее. Снова нужно дополнить число нулями до длины n. На этот раз нужно будет вставить десять палочек, чтобы разделить одиннадцать групп – нули встречаются в начале и в конце числа. Числа отображаются в строки аналогично, но нет однозначного соответствия для нуля. Одному нулю соответствуют n + 1 строка. Это все строки в которых все десять палочек собраны вместе. Количество возрастающих чисел равно C_n+10¹⁰ - n.

Код

Функция cnk вычисляет число сочетаний по формулам:

• C_n⁰ = 1;
• C_n+1^k+1 = (n + 1)C_n^k / (k + 1).

#include <iostream>

unsigned long long cnk(unsigned long long n, unsigned long long k) {
    unsigned long long p = 1;
    for (unsigned long long i = 1; i <= k; ++i) {
        p = p * (n - k + i) / i;
    }
    return p;
}

unsigned long long mono(unsigned n) {
    return cnk(n + 9, 9) + cnk(n + 10, 10) - 10 * n - 1;
}

int main() {
    unsigned n;
    if (std::cin >> n) {
        std::cout << mono(n) << '\n';
    }
}

Этот код решает задачу для n ≤ 298. Дальше возникает переполнение. Если хотите увеличить диапазон, в этом ответе есть cnk, которая решит задачу для n ≤ 375, так же как вариант в главке Динамическое программирование.