blob: 91015d0c5ce67fe2b245669c82a38c3539625ca5 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include "leetcode.h"
class Solution {
public:
string largestNumber(vector<int> &cost, int target) {
vector<int> dp(target + 1, -10000);
dp[0] = 0;
for (int i = 1; i <= target; ++i)
for (int j = 0; j < 9; ++j)
dp[i] = max(dp[i], i >= cost[j] ? 1 + dp[i - cost[j]] : -10000);
if (dp[target] < 0)
return "0";
string ans = "";
for (int i = 8; i >= 0; --i) {
while (target >= cost[i] && dp[target] == dp[target - cost[i]] + 1) {
ans.push_back('1' + i);
target -= cost[i];
}
}
return ans;
}
};
int main() {
Solution obj;
vector<int> cost = {4, 3, 2, 5, 6, 7, 2, 5, 5};
int target = 9;
cout << obj.largestNumber(cost, target);
}
|