leetcode 322

题目

例子

思路

记忆化搜索，使用数组，记录val的最少硬币数量；
递归加bfs;

代码实现

#include <vector>
#include <climits> // For INT_MAX
#include <algorithm> // For min

class Solution {
public:
    int step = 0;
    std::vector<int> dp_mem;

    int bfs(std::vector<int>& coins, int remain) {
        if (remain == 0) {
            return 0;
        }

        if (remain < 0) {
            return -1;
        }

        if (dp_mem[remain] != INT_MAX) {
            return dp_mem[remain];
        }

        int minSteps = INT_MAX;
        for (int c : coins) {
            int res = bfs(coins, remain - c);
            if (res != -1) {
                minSteps = std::min(minSteps, res + 1);
            }
        }

        dp_mem[remain] = (minSteps == INT_MAX) ? -1 : minSteps;
        return dp_mem[remain];
    }

    int coinChange(std::vector<int>& coins, int amount) {
        dp_mem.resize(amount + 1, INT_MAX);
        return bfs(coins, amount);
    }
};

详解

dp_mem[1] 只有选择coin 1, dp_mem[2] 是选择 coin 2 而不是2个coin 1,一次类推，所以实际上是遍历所有组合数，然后不断更新最优组合数。逆推用递归，正推就是遍历。

时间复杂度 O(S * n)， S是amount， n是硬币种类。