aboutsummaryrefslogtreecommitdiff
path: root/other/largest_int_add_target.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/largest_int_add_target.cpp')
-rw-r--r--other/largest_int_add_target.cpp29
1 files changed, 0 insertions, 29 deletions
diff --git a/other/largest_int_add_target.cpp b/other/largest_int_add_target.cpp
deleted file mode 100644
index 91015d0..0000000
--- a/other/largest_int_add_target.cpp
+++ /dev/null
@@ -1,29 +0,0 @@
-#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);
-}