#include "leetcode.h" class Solution { public: string largestNumber(vector &cost, int target) { vector 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 cost = {4, 3, 2, 5, 6, 7, 2, 5, 5}; int target = 9; cout << obj.largestNumber(cost, target); }