自动售货机买东西

20210720，今天重做了，之前做的简直跟S一般，这种题目得用dp+cache啊，ms真是一家了不起的公司，对人友好，题目有意思

#include <iostream>
#include <vector>
#include <map>

/*
用最少数量的钱买商品
*/

class Solution {
public:
    std::vector<int> buy_goods(const std::vector<int>& money, int price) {
        std::map<int, std::vector<int>> cache;
        return dp(money, price, cache);
    }

    std::vector<int> dp(const std::vector<int>& money, int price, std::map<int, std::vector<int>>& cache) {
        if (price <= 0)
            return std::vector<int>();

        for (auto i : money) {
            if (price == i) {
                return std::vector<int>(1, i);
            }
        }

        auto it = cache.find(price);
        if (it != cache.end())
            return it->second;

        std::vector<int> result;
        for (auto i : money) {
            auto this_result = dp(money, price - i, cache);
            if (this_result.size() == 0)
                continue;

            if (result.size() == 0) {
                result = this_result;
                result.push_back(i);
            } else if (this_result.size() < result.size()) {
                result = this_result;
                result.push_back(i);
            }
        }

        cache[price] = result;
        return result;
    }
};

int main() {
    std::vector<int> money;
    for (int i = 0; i < 3; i++)
        money.push_back(100);
    for (int i = 0; i < 3; i++)
        money.push_back(10);
    for (int i = 0; i < 3; i++)
        money.push_back(5);
    for (int i = 0; i < 3; i++)
        money.push_back(2);
    auto result = Solution().buy_goods(money, 32);
    return 0;
}

之前用排列的方式来做，时间复杂度高到极点