【Leetcode】1449. Form Largest Integer With Digits That Add up to Target

题目地址：

https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/

考虑$1\sim 9$这$9$个数字，给定每个数字的代价，和一个总代价$t$，问恰好用尽$t$的情况下，能组成的最大数字是多少。如果无解则返回$0$。

能组成的数字一定是正整数，所以位数越多越大。在位数最大的情况下，字典序越大数字越大。所以问题就变为，恰好用完$t$的代价，最多能得到几位数，在位数最多的情况下，字典序最大可以得到多少。同一个数字允许用多次，从而本质上是个完全背包问题。设$f[k][s]$是只考虑$1\sim k$，且总代价恰好为$s$的情况下能取得的最大位数，则可以按照$k$取不取来分类，所以： f [ k ] [ s ] = max ⁡ { f [ k − 1 ] [ s ] , f [ k ] [ s − c [ k ] ] + 1 } f[k][s]=\max\{f[k-1][s],f[k][s-c[k]]+1\} f[k][s]=max{f[k−1][s],f[k][s−c[k]]+1}$c[k]$为$k$的代价。推完$f$之后，从后向前推，对于$f[k][s]$，如果$f[k-1][s]>f[k][s-c[k]]+1$，那么$k$是不能取的，否则由于要字典序更大，要取$k$。代码如下：

class Solution {
 public:
  string largestNumber(vector<int>& cost, int target) {
    int f[10][target + 1];
    memset(f, -1, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= 9; i++)
      for (int j = 0; j <= target; j++) {
        f[i][j] = f[i - 1][j];
        if (j >= cost[i - 1] && ~f[i][j - cost[i - 1]]) 
          f[i][j] = max(f[i][j], f[i][j - cost[i - 1]] + 1);
      }

    if (f[9][target] == -1) return "0";

    string res;
    for (int i = 9, j = target; i; i--)
      while (j >= cost[i - 1] && f[i][j] == f[i][j - cost[i - 1]] + 1) {
        res += to_string(i);
        j -= cost[i - 1];
      }

    return res;
  }
};
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

时空复杂度$O(t)$。