【C++动态规划 01背包】2787. 将一个数字表示成幂的和的方案数

本文涉及知识点

C++动态规划
C++背包问题

LeetCode2787. 将一个数字表示成幂的和的方案数

给你两个 正 整数 n 和 x 。
请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说,你需要返回互不相同整数 [n1, n2, …, nk] 的集合数目,满足 n = n1x + n2x + … + nkx 。
由于答案可能非常大,请你将它对 109 + 7 取余后返回。
比方说,n = 160 且 x = 3 ,一个表示 n 的方法是 n = 23 + 33 + 53 。
示例 1:
输入:n = 10, x = 2
输出:1
解释:我们可以将 n 表示为:n = 32 + 12 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。
示例 2:
输入:n = 4, x = 1
输出:2
解释:我们可以将 n 按以下方案表示:

  • n = 41 = 4 。
  • n = 31 + 11 = 4 。
    提示:
    1 <= n <= 300
    1 <= x <= 5

动态规划之01背包

本问题 KaTeX parse error: Undefined control sequence: \iif at position 1: \̲i̲i̲f̲ i号背包的容量为ix,求容量为n的方案数。由于x >=1,如果i1 > N, 则i1x >N。故不需要尝试i1号背包。空间复杂度:O(NN)

动态规划的状态表示

dp[i][n]表示[1…i]号背包容量为n的方案数。

动态规划的转移方程

枚举i号背包是否选取
cur = dp[i] pre=dp[i-1]
cur = pre 不需要i号背包
cur[n+ix] += pre[n]
时间复杂度:O(nnn)

动态规划的填报顺序

i = 1 to (ix<=n)

动态规划的初始值

dp[0][0]=1,其它全为0。

动态规划的返回值

dp.back().back()

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:C1097Int(long long llData = 0) :m_iData(llData% MOD){}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((long long)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((long long)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = (m_iData + MOD - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o){return C1097Int((m_iData + MOD - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((long long)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((long long)m_iData * o.m_iData) % MOD;return *this;}C1097Int  operator/(const C1097Int& o)const{return *this * o.PowNegative1();}C1097Int& operator/=(const C1097Int& o){*this /= o.PowNegative1();return *this;}bool operator==(const C1097Int& o)const{return m_iData == o.m_iData;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(long long n)const{C1097Int iRet = 1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}int ToInt()const{return m_iData;}
private:int m_iData = 0;;
};class Solution {public:int numberOfWays(int n, int x) {vector<vector<C1097Int<>>> dp(n + 1, vector<C1097Int<>>(n + 1));dp[0][0] = 1;for (int i = 1; i <= n; i++) {dp[i] = dp[i - 1];for (int j = 0; j <= n; j++) {double d = 0.5 + pow(i, x);if (d > INT_MAX)continue;const auto sum = j + (int)d;if (sum > n) { continue; }dp[i][sum] += dp[i - 1][j];}}return dp.back().back().ToInt();}};

核心代码

int n,x;TEST_METHOD(TestMethod11){n = 10, x = 2;auto res = Solution().numberOfWays(n, x);AssertEx(1, res);}TEST_METHOD(TestMethod12){n = 4, x = 1;auto res = Solution().numberOfWays(n, x);AssertEx(2, res);}TEST_METHOD(TestMethod13){n = 74, x = 5;auto res = Solution().numberOfWays(n, x);AssertEx(0, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/461775.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python爬虫的京东大冒险:如何高效获取商品详情的秘籍

在这个由代码编织的电商世界里&#xff0c;京东商品详情就像是被锁在高塔中的公主&#xff0c;等待着勇敢的Python爬虫骑士去解救。今天&#xff0c;我们要讲述的是如何成为一名Python爬虫骑士&#xff0c;携带你的代码长矛&#xff0c;穿梭在API的数据森林中&#xff0c;高效获…

SpringBoot【实用篇】- 测试

文章目录 目标&#xff1a;1.加载测试专用属性3.Web环境模拟测试2.加载测试专用配置4.数据层测试回滚5.测试用例数据设定 目标&#xff1a; 加载测试专用属性加载测试专用配置Web环境模拟测试数据层测试回滚测试用例数据设定 1.加载测试专用属性 我们在前面讲配置高级的时候…

vfx特效有多烧钱?云渲染农场减少vfx特效成本

特效制作一直是电影制作中的烧钱大户&#xff0c;尤其是视觉特效&#xff08;VFX&#xff09;的高昂成本让许多项目望而却步。但随着云渲染农场技术的发展&#xff0c;VFX特效的成本得到了有效控制&#xff0c;为电影工业带来了革命性的变化。 在电影工业中&#xff0c;VFX特效…

任何python安装gdal出现的问题

Releases cgohlke/geospatial-wheels GitHubGeospatial library wheels for Python on Windows. Contribute to cgohlke/geospatial-wheels development by creating an account on GitHub.https://github.com/cgohlke/geospatial-wheels/releases 各种乱七八糟的gdal库问题…

tensorflow案例4--人脸识别(损失函数选取,调用VGG16模型以及改进写法)

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 前言 这个模型结构算上之前的pytorch版本的&#xff0c;算是花了不少时间&#xff0c;但是效果一直没有达到理想情况&#xff0c;主要是验证集和训练集准确率…

SPA和SSR

单页面应用程序(SPA) 单页面应用(SPA)全称是:Single-page application, SPA应用是在客户端呈现的(术语称:CRS)。 SPA应用默认只返回一个空HTML页面&#xff0c;如:body只有<div id"app"></div>而整个应用程序的内容都是通过JavaScript动态加载&#xf…

【 纷享销客-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…

基于SpringBoot和PostGIS的世界各国邻国可视化实践

目录 前言 一、空间数据查询基础 1、空间数据库基础 2、空间相邻查询 二、SpringBoot后台功能设计 1、后台查询接口的实现 2、业务接口设计 三、Leaflet进行WebGIS开发 1、整体结构介绍 2、相邻国家展示可视化 四、成果展示 1、印度及其邻国 2、乌克兰及其邻国 3、…

Python之groupby()及aggregate()方法

目录 数据准备df.describe()思考1 分组 pd.groupby()思考2 df.aggregate()思考1 现在有一份titanic_train.csv&#xff0c;包含泰坦尼克号乘客信息及获救情况的明细数据&#xff0c;我们需要使用一些聚合函数&#xff0c;统计相关指标。 数据准备 import pandas as pd df pd.…

Unity 二次元三渲二

三渲二 注意&#xff1a;Unity必须是2022.3LTS及以上和URP项目&#xff01;&#xff01;&#xff01; 下载三渲二插件 【如何将原神的角色导入Unity】全网最细致教程&#xff0c;全程干货。不使用任何收费插件&#xff0c;使用Spring Bone对头发和衣服进行物理模拟。_原神 步…

Unity计算二维向量夹角余弦值和正弦值的优化方法参考

如果不考虑优化问题&#xff0c;计算两个向量的余弦值或者正弦值可以直接使用类似的方法&#xff1a; [SerializeField] Vector2 v1, v2;void Start() {float valCos Mathf.Acos(Vector2.SignedAngle(v1, v2));float valSin Mathf.Asin(Vector2.SignedAngle(v1, v2)); } 但是…

深度|谁在为OpenAI和Anthropic的AI编程竞赛提供“军火”?已赚得盆满钵满

图片来源&#xff1a;Unsplash AI 开发者之所以一致认为编程的重要性&#xff0c;是有原因的&#xff1a;大型语言模型编程能力越强&#xff0c;它回答与软件无关的其他类型问题的能力也越强。 去年秋天&#xff0c;几位 Google 人工智能领导者与初创公司 CEO Jonathan Siddh…

2024年北京市安全员-A证证模拟考试题库及北京市安全员-A证理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年北京市安全员-A证证模拟考试题库及北京市安全员-A证理论考试试题是由安全生产模拟考试一点通提供&#xff0c;北京市安全员-A证证模拟考试题库是根据北京市安全员-A证最新版教材&#xff0c;北京市安全员-A证大…

[ 问题解决篇 ] win11中本地组策略编辑器gpedit.msc打不开(gpedit.msc缺失)

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…

前端聊天室页面开发(赛博朋克科技风,内含源码)

肝了一天&#xff0c;经过各种处理美化&#xff0c;肝出来了一个赛博朋克科技风的前端页面&#xff0c;用的原生三件套htmlcssjavascript开发的&#xff0c;本来想是加点功能调用一下gpt接口&#xff0c;但是基本都需要webscoket通信&#xff0c;可惜我js学的不是很深入&#x…

TMDOG的Gin学习笔记_01——初识Gin框架

TMDOG的Gin学习笔记_01——初识Gin框架 博客地址&#xff1a;[TMDOG的博客](https://blog.tmdog114514.icu) 作者自述&#xff1a; 停更太久了&#xff0c;是因为开学了课太多了&#xff0c;并且我一直在准备上篇文章的内容正在coding&#xff0c;就先搁置了更新博客QAQ&…

wsl2.0(windows linux子系统)使用流程

1.什么是wsl wsl指的是windows的linux子系统&#xff0c;最初是wsl1.0&#xff0c;靠windows内核来模拟linux内核&#xff0c;并不运行真正的linux内核&#xff0c;所以有时会有兼容性的问题。 而wsl2.0是基于windows自带的虚拟机功能hyper-v的&#xff0c;它会把设备上的每个…

计算机网络:网络层 —— IPv4 数据报的首部格式

文章目录 IPv4数据报的首部格式IPv4数据报分片生存时间 TTL字段协议字段首部检验和字段 IPv4数据报的首部格式 IPv4 数据报的首部格式及其内容是实现 IPv4 协议各种功能的基础。 在 TCP/IP 标准中&#xff0c;各种数据格式常常以32比特(即4字节)为单位来描述 固定部分&#x…

vue3学习记录-nextTick

vue3学习记录-nextTick 1. 案例场景2. 使用方法2.1 回调方式2.2 async&#xff0c;await 3.原理 1. 案例场景 聊天框实现输入内容&#xff0c;滚动条默认滚到最底部。 <template><div class"chat_box"><div class"chat_list" ref"chat…

Facebook群控策略详解

Facebook群控早在前几年就很火爆了&#xff0c;对于做Facebook营销或者电商的跨境选手来说&#xff0c;这是个不错的提高效率扩大增长的办法。具体来说&#xff0c;Facebook群控是一种通过同时管理多个Facebook账户进行自动化推广活动的方法&#xff0c;它可以实现自动发布帖子…