Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.
dp[i]
表示要凑成金额 i
最少需要的硬币数class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (empty(coins)) {
return -1;
}
// 假设全用 1 也不可能用 amout + 1 个,用初始值表示无法组合
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (auto& x : coins) {
if (i >= x) {
dp[i] = min(dp[i], dp[i - x] + 1);
}
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
};