本文涉及知识点

动态规划汇总
C++背包问题
数学

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大，则表示的数大。
状态数：O(cost.length target)

动态规划的转移方程

v1 = v ;
v1[0]++,v1[10-j]++
dp[i+ cost [j-1] =max($\cdots$,v1)
转移时间复杂度O(1)，故总时间复杂度O(cost.length target)

动态规划的初始值

dp[0][0]为0，dp[?][0]为-10000。其它为0。

动态规划的填表顺序

第一层循环：枚举9到1。
第二层循环：枚举各状态。
可以这样理解：第一层枚举的是最小的数，第二层枚举的是除了最小数外的数。
不需要枚举: “” $\to$ “777”
只需要枚举 “” $\to$ “7” $\to$ “77” $\to$ “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;
}
}