Минимальная смена монет - Dynami c Программирование

Question

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

Мой подход - я следовал нисходящему подходу, но с запоминанием с использованием карты stl, Я получаю TLE. Пожалуйста, помогите найти ошибку и оценить сложность времени.

Вот мой код -

// for example coins v = {1,2} and W = 2 then possible solutions are -
// (2) or (1, 1), therefore minimum number of coins required is 1.
// Below is the function calculating the minimum number of coins required for change

int minCoinChange(vector<int> &v, int start, int W, unordered_map<string, int> &lookup){

// v denoting the vector conataining coins with given denomination
// start denoting the start index i.e. 0(initially)
// W denoting the required change
// lookup is map stl for storing values.

// base cases 
    if(W<0){
        return INT_MAX;
    }
    if(W == 0){
        return 0;
    }
    if(start >= v.size()){
        return INT_MAX;
    }

// for memoization creating the "key"
    string key = to_string(start) + '|' + to_string(W);

// if the key is not found in map then go inside if 
    if(lookup.find(key) == lookup.end()){
        int excl = minCoinChange(v, start+1, W, lookup); // if element is excluded

        int incl = 1 + minCoinChange(v, start, W - v[start], lookup); if element is included 

        lookup[key] = min(incl, excl); // calculating minimum number of coins required and storing in map 
    }
// if key is already there then return value stored in map 
    return lookup[key]; 
}

Answer 1

Прежде всего, unordered_map имеет худший случай O(n) время поиска. Есть способы оптимизировать производительность unordered_map, например, зарезервировать количество сегментов, используя map.reserve(n), где n - это число уникальных элементов, которые вы ожидаете иметь на карте.

Вы можете вместо этого используйте map, который имеет худший случай O(log(n)) время поиска, но поскольку временная сложность этого алгоритма O(n * W), ваши n и W будут достаточно малы, чтобы поместиться в массив, и тогда у вас будет O(1) посмотрите вместо этого.

Ниже приведена модификация вашей функции для использования поиска по массиву:

int minCoinChange(vector<int> &v, int start, int W, vector<vector<int>> &lookup){

    // v denoting the vector conataining coins with given denomination
    // start denoting the start index i.e. 0(initially)
    // W denoting the required change
    // lookup is 2d vector for storing already computed values.

    // base cases 
    if (W<0) {
        return 1e9;
    }
    if (W == 0) {
        return 0;
    }
    if (start >= v.size()) {
        return 1e9;
    }

    // if this state wasn't computed before
    if (lookup[start][W] == -1) {
        int excl = minCoinChange(v, start+1, W, lookup); // if element is excluded

        int incl = 1 + minCoinChange(v, start, W - v[start], lookup); // if element is included 

        lookup[start][W] = min(incl, excl); // calculating minimum number of coins required and storing in map 
    }
    // return the saved value
    return lookup[start][W];
}

Примечание:

Для базовых случаев вместо использования INT_MAX, который будет переполнен, если вы добавите 1 к нему, используйте что-то вроде 10^9.