leetcode 322

题目

例子

思路

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

代码实现

#include <vector>
#include <climits> // For INT_MAX
#include <algorithm> // For minclass 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是硬币种类。