aboutsummaryrefslogtreecommitdiff
path: root/largest_int_add_target.cpp
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);
}