作者推荐
【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目
本文涉及知识点
LeetCode1449. 数位成本和为目标值的最大数字
给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：
给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。
如果按照上述要求无法得到任何整数，请你返回 “0” 。
示例 1：
输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出：“7772”
解释：添加数位 ‘7’ 的成本为 2 ，添加数位 ‘2’ 的成本为 3 。所以 “7772” 的代价为 23+ 31 = 9 。 “977” 也是满足要求的数字，但 “7772” 是较大的数字。
数字 成本
1 -> 4
2 -> 3
3 -> 2
4 -> 5
5 -> 6
6 -> 7
7 -> 2
8 -> 5
9 -> 5
示例 2：
输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出：“85”
解释：添加数位 ‘8’ 的成本是 7 ，添加数位 ‘5’ 的成本是 5 。“85” 的成本为 7 + 5 = 12 。
示例 3：
输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出：“0”
解释：总成本是 target 的条件下，无法生成任何整数。
示例 4：
输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出：“32211”
提示：
cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000
动态规划的状态表示
dp[i] = v 表示成本为i能够表示的最大数。v有10个元素，v[0]表示总数量,v[1]到V[9]表示9到1的数量。
v[0] = -10000。表示非法。 v大，则表示的数大。
动态规划的转移方程
v1 = v ;
v1[0]++,v1[10-j]++
dp[i+ cost [j-1] =max(⋯ \cdots⋯,v1)
动态规划的初始值
dp[0][0]为0，dp[?][0]为-10000。其它为0。
动态规划的填表顺序
第一层循环：枚举9到1。
第二层循环：枚举各状态。
可以这样理解：第一层枚举的是最小的数，第二层枚举的是除了最小数外的数。
不需要枚举: “” → \rightarrow→ “777”
只需要枚举 “” → \rightarrow→ “7” → \rightarrow→ “77” → \rightarrow→ “777”
动态规划的返回值
dp[target] 转成字符串。
代码
核心代码
class Solution { public: string largestNumber(vector<int>& cost, int target) { vector<vector<int>> dp(target+1, vector<int>(10)); for (int i = 1; i <= target; i++) { dp[i][0] = -10'000; } for (int j = 9; j >= 1; j--) { for (int cost0 = 0; cost0 <= target; cost0++) { const int cost1 = cost0 + cost[j - 1]; if (cost1 > target) { continue; } auto v1 = dp[cost0]; v1[0]++; v1[10 - j]++; dp[cost1] = max(dp[cost1], v1); } } if (dp.back()[0] < 0) { return "0"; } string strRet; for (int i = 1; i <= 9; i++) { strRet += string(dp.back()[i], '0' + 10 - i); } return strRet; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> cost; int target; { Solution sln; cost = { 4, 3, 2, 5, 6, 7, 2, 5, 5 }, target = 9; auto res = sln.largestNumber(cost, target); Assert(string("7772"), res); } { Solution sln; cost = { 7, 6, 5, 5, 5, 6, 8, 7, 8 }, target = 12; auto res = sln.largestNumber(cost, target); Assert(string("85"), res); } { Solution sln; cost = { 2,4,6,2,4,6,4,4,4 }, target = 5; auto res = sln.largestNumber(cost, target); Assert(string("0"), res); } }
2023年2月
class Solution {
public:
string largestNumber(vector& cost, int target) {
vector pre(target + 1, -10000);
vector<vector> preNums(target + 1,vector(10));
pre[0] = 0;
for (int i = 1; i <= 9; i++)
{
vector dp = pre;
vector<vector> nums = preNums;
const int iCost = cost[i - 1];
for (int j = iCost; j <= target; j++)
{
if (dp[j - iCost] + 1 >= dp[j])
{
dp[j] = dp[j - iCost] + 1;
nums[j] = nums[j - iCost];
nums[j][i]++;
}
}
pre.swap(dp);
preNums.swap(nums);
}
if (pre[target] <= 0)
{
return string(“0”);
}
string str;
for (int i = 9; i >= 1; i-- )
{
str += string(preNums[target][i], i + ‘0’);
}
return str;
}
};
2023年7月
class Solution {
public:
string largestNumber(vector& cost, int target) {
vector<vector> dp(target + 1);
dp[0].resize(10);//dp[0][0]表示1到9的数量dp[0][1]表示9的数量，dp[1][2]表示8的数量…
for (int i = 8 ; i >= 0 ; i–)
{
for (int j = 0; j + cost[i] <= target; j++)
{
vector pre = dp[j];
if (0 == pre.size())
{
continue;
}
pre[0]++;
pre[9 - i]++;
auto& cur = dp[j + cost[i]];
if (0 == cur.size() || (cur < pre))
{
cur = pre;
}
}
}
if (0 == dp.back().size())
{
return “0”;
}
string str;
for (int i = 1; i < dp.back().size(); i++)
{
str += string(dp.back()[i], 10 - i + ‘0’);
}
return str;
}
};
