Алгоритм получения чисел из спичечных палочек

Я сделал программу для решения этой проблемы из ACM.

Спички - идеальный инструмент для представления чисел. Распространенный способ представления десяти десятичных цифр спичками следующий:

Это идентично тому, как числа отображаются в обычном будильнике. С заданным количеством спичек вы можете создать широкий диапазон чисел. Нам интересно, какие наименьшие и наибольшие числа можно создать, используя все ваши спички.

Входные данные

В первой строке одно положительное число: количество тестов, не более 100. После этого для каждого теста:

Одна строка с целым числом n (2 ≤ n ≤ 100): количество имеющихся у вас спичек. Выходные данные

Для теста:

Одна строка с наименьшим и наибольшим числами, которые вы можете создать, разделенные одним пробелом. Оба числа должны быть положительными и не содержать ведущих нулей. Пример ввода

4 3 6 7 15 Пример вывода

7 7 6 111 8 711 108 7111111

Проблема в том, что решить ее за 100 спичек слишком медленно. Дерево поиска слишком велико для перебора.

Вот результаты для первых 10:

2: 1 1

3: 7 7

4: 4 11

5: 2 71

6: 6 111

7: 8 711

8: 10 1111

9: 18 7111

10: 22 11111

Шаблон для максимумов прост, но я не см. ярлык для минимума. Может кто-нибудь предложить лучший способ решить эту проблему? Вот код, который я использовал:

    #include 
    #include 
    using namespace std;

    #define MAX 20 //should be 100

    //match[i] contains number of matches needed to form i
    int match[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    string mi[MAX+1], ma[MAX+1];
    char curr[MAX+1] = "";

    //compare numbers saved as strings
    int mycmp(string s1, string s2)
    {
        int n = (int)s1.length();
        int m = (int)s2.length();
        if (n != m)
            return n - m;
        else
            return s1.compare(s2);
    }

    //i is the current digit, used are the number of matchsticks so far
    void fill(int i, int used)
    {
        //check for smaller and bigger values
        if (mycmp(curr, mi[used]) < 0) mi[used] = curr;
        if (mycmp(curr, ma[used]) > 0) ma[used] = curr;

        //recurse further, don't start numbers with a zero
        for (int a = i ? '0' : '1'; a <= '9'; a++) {
            int next = used + match[a-'0'];
            if (next <= MAX) {
                curr[i] = a;
                curr[i+1] = '\0';
                fill(i + 1, next);
            }
        }
    }

    int main()
    {
        //initialise 
        for (int i = 0; i <= MAX; i++) {
            mi[i] = string(MAX, '9');
            ma[i] = "0";
        }

        //precalculate the values
        fill(0, 0);

        int n;
        cin >> n;

        //print those that were asked
        while (n--) {
            int num;
            cin >> num;
            cout << mi[num] << " " << ma[num] << endl;
        }

        return 0;
    }

РЕДАКТИРОВАТЬ : В итоге я использовал решение для динамического программирования. Я пробовал это с dp раньше, но я возился с двумерным массивом состояний. Решения здесь намного лучше. Спасибо!