1.题目描述

2.代码实现

主要思路：类似零钱兑换

#include <iostream>
#include <vector>
using namespace std;class Solution {
public:int buyNails(vector<int>& nails, int count) {vector<int> dp(count+1, -1);dp[0] = 0;for(int i = 1; i <= count; i++){for(int j = 0; j < nails.size(); j++){if(i - nails[j] >= 0 && dp[i-nails[j]] != -1){if(dp[i] == -1 || dp[i] > dp[i-nails[j]]+1)dp[i] = dp[i-nails[j]] + 1;}}}return dp[count];}
};int main()
{vector<int> nails = {4, 9};int n;cin >> n;Solution s;cout << s.buyNails(nails, n) <<endl;;return 0;
}