数位成本和为目标值的最大数字
题面
leetcode题目
给你一个整数数组 \(cost\) 和一个整数 \(target\) 。请你返回满足如下规则可以得到的 最大 整数：
- 给当前结果添加一个数位\(（i + 1）\)的成本为 \(cost[i]\) （\(cost\) 数组下标从 \(0\) 开始）。
- 总成本必须恰好等于 \(target\) 。
- 添加的数位中没有数字 \(0\) 。
由于答案可能会很大，请你以字符串形式返回。
如果按照上述要求无法得到任何整数，请你返回 "0" 。
example
输入：\(cost = [4,3,2,5,6,7,2,5,5]\), \(target = 9\)
输出："7772"
解释：添加数位 '7' 的成本为 \(2\) ，添加数位 '2' 的成本为 \(3\) 。所以 "7772" 的代价为 \(2\times 3+ 3\times 1 = 9\) 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。
数字 成本
1 -> 4
2 -> 3
3 -> 2
4 -> 5
5 -> 6
6 -> 7
7 -> 2
8 -> 5
9 -> 5
数据范围
- \(cost.length == 9\)
- \(1 \leq cost[i] \leq 5000\)
- \(1 \leq target \leq 5000\)
题解
总体思路
考虑\(dp[i][j]\)表示当\(target = i\)时的最大数字对应的数字\(j\)有\(dp[i][j]\)个，那么有: \[ tmp_k[i][j] = \left\{
\begin{array}{rcl}
dp[i-cost[k]][j] & & { cost [k] \leq i \land }\\
dp[i-cost[k]][j] + 1 & & {cost [k] \leq i \land k + 1 = j }
\end{array} \tag{1}\right.
\] 则: \[ dp[i][j] = max(tmp_k[i][j]) \qquad k \in \{0,1,2,3,4,5,6,7,8\} \tag{2}\] 那么现在我们只需要考虑\(max\)如何取得才能满足构成最大数字就能实现闭环。我们这样考虑：对于\(tmp_a[i]\)与\(tmp_b[i]\)，只要有:
- \(sum_{k=1}^{9} tmp_a[i] > sum_{k=1}^{9} tmp_b[i]\)
- \(tmp_a[i][j] > tmp_b[i][j]\) 且\(j\)为从\(9\)到\(1\)第一个满足\(tmp_a[i][j]\neq tmp_b[i][j]\)的数 两个条件之一，则可表示$tmp_a[i] > \(tmp_b[i]\)。
这是因为:
- 如果满足条件1，那么我们总是可以将\(tmp_a[i]\)表示成一个位数比\(tmp_b[i]\)多的数，自然是比较大的。
- 如果满足条件2，我们从9开始往1构造，大的数在前，由于存在一个数在\(tmp_a[i]\)与\(tmp_b[i]\)中位数不同且前者多，那么此时可以明显的得到某一个高位前者是要大一些的。
代码
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
| #include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <string>
using namespace std;
#define _DEBUG
class Solution
{
public:
string largestNumber(vector<int> &cost, int target)
{
int dp[target + 1][10];
memset(dp, 0, sizeof(dp));
dp[0][0] = -1;
for (int i = 1; i \leq target; i++)
{
int max[10] = {0};
int tmp[10] = {0};
for (int j = 0; j < cost.size(); j++)
{
int idx = j + 1;
int val = cost[j];
if (val \leq i && dp[i - val][0] == -1)
{
for (int k = 0; k < 10; k++)
{
tmp[k] = dp[i - val][k];
}
tmp[idx]++;
bool swap = true;
int cnt1, cnt2;
cnt1 = cnt2 = 0;
#ifdef _DEBUG
cout << "target: " << target << " i: " << i << " j: " << j << " val: " << val << endl;
for (int t = 1; t \leq 9; t++)
{
cout << tmp[t] << " ";
}
cout << endl;
#endif
for (int k = 9; k >= 1; k--)
{
cnt1 += max[k];
cnt2 += tmp[k];
#ifdef _DEBUG
cout << "max[k]: " << max[k] << " tmp[k]: " << tmp[k] << " cnt1: " << cnt1 << " cnt2: " << cnt2 << endl;
#endif
}
#ifdef _DEBUG
cout << "cnt1: " << cnt1 << " cnt2: " << cnt2 << endl;
#endif
if (cnt1 > cnt2)
{
swap = false;
}
else if (cnt1 < cnt2)
{
swap = true;
}
else if (cnt1 == cnt2)
{
for (int k = 9; k >= 1; k--)
{
cnt1 += max[k];
cnt2 += tmp[k];
if (max[k] > tmp[k])
{
swap = false;
break;
}
else if (max[k] < tmp[k])
{
break;
}
}
}
if (swap)
{
for (int k = 0; k < 10; k++)
{
max[k] = tmp[k];
}
}
dp[i][0] = -1;
}
}
for (int k = 1; k < 10; k++)
{
dp[i][k] = max[k];
}
#ifdef _DEBUG
cout << " i: " << i << endl;
for (int t = 1; t \leq 9; t++)
{
cout << tmp[t] << " ";
}
cout << endl;
cout << endl;
#endif
}
string ret = "";
for (int k = 9; k >= 1; k--)
{
int cnt = dp[target][k];
for (int r = 0; r < cnt; r++)
{
ret += ('0' + k);
}
}
if (ret == "")
{
ret += "0";
}
return ret;
}
};
int main()
{
Solution s;
vector<int> t1{4, 3, 2, 5, 6, 7, 2, 5, 5};
cout << s.largestNumber(t1, 9) << endl;
return 0;
}
|