【动态规划】【数学】【C++算法】1449. 数位成本和为目标值的最大数字

本文主要是介绍【动态规划】【数学】【C++算法】1449. 数位成本和为目标值的最大数字,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者推荐

【深度优先搜索】【树】【图论】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;
}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

这篇关于【动态规划】【数学】【C++算法】1449. 数位成本和为目标值的最大数字的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/707382

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

使用PyTorch实现手写数字识别功能

《使用PyTorch实现手写数字识别功能》在人工智能的世界里,计算机视觉是最具魅力的领域之一,通过PyTorch这一强大的深度学习框架,我们将在经典的MNIST数据集上,见证一个神经网络从零开始学会识... 目录当计算机学会“看”数字搭建开发环境MNIST数据集解析1. 认识手写数字数据库2. 数据预处理的

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque