货币找零问题求解

实用动态规划+缓存，完美解决

#include <stdio.h>
#include <vector>
#include <map>

/*
考虑币值为 100 ， 99 和 1 的币种，每种各一百张，找 396 元
*/

class Solution {
public:
    std::vector<int> GetResult(const std::vector<int>& cash, int target) {
        std::map<int, std::vector<int>> cache;
        return get_result(cash, target, cache);
    }

    std::vector<int> get_result(const std::vector<int>& cash, int target, std::map<int, std::vector<int>>& cache) {
        if (target <= 0)
            return std::vector<int>();

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

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

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

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

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

int main() {
    std::vector<int> cash;
    cash.push_back(1);
    cash.push_back(99);
    cash.push_back(100);

    auto ret = Solution().GetResult(cash, 396);
    return 0;
}