[C++][算法基础]整数划分(统计动态规划)

一个正整数 𝑛 可以表示成若干个正整数之和,形如:𝑛=𝑛1+𝑛2+…+𝑛𝑘,其中 𝑛1≥𝑛2≥…≥𝑛𝑘,𝑘≥1。

我们将这样的一种表示称为正整数 𝑛 的一种划分。

现在给定一个正整数 𝑛,请你求出 𝑛 共有多少种不同的划分方法。

输入格式

共一行,包含一个整数 𝑛。

输出格式

共一行,包含一个整数,表示总划分数量。

由于答案可能很大,输出结果请对 10^{9}+7 取模。

数据范围

1≤𝑛≤1000

输入样例:
5
输出样例:
7

 代码:

1. 二维数组做法(完全背包)

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];

int CountDP(){
    for(int i = 0;i <= n;i ++){
         f[i][0] = 1;
    }
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= n;j ++){
            if(j >= i){
                f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
            }else{
                f[i][j] = f[i - 1][j];
            }
            
        }
    }
    return f[n][n];
}

int main(){
    cin>>n;
    int res = CountDP();
    cout<<res<<endl;
    return 0;
}

2. 一维数组做法(完全背包)

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];

int CountDP(){
    for(int i = 0;i <= n;i ++){
         f[0] = 1;
    }
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= n;j ++){
            if(j >= i){
                f[j] = (f[j] + f[j - i]) % mod;
            }else{
                f[j] = f[j];
            }
            
        }
    }
    return f[n];
}

3. 优化做法(以最小值1为界划分)

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];

int CountDP(){
    f[0][0] = 1;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= i;j ++){
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
        }
    }
    int res = 0;
    for(int i = 1;i <= n;i ++){
        res = (res + f[n][i]) % mod;
    }
    return res;
}

int main(){
    cin>>n;
    int res = CountDP();
    cout<<res<<endl;
    return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SDB2F5 1.5A,高达28V输出1.2MHz升压转换器芯片IC

一般说明 该SDB2F5是一个恒定的频率&#xff0c;5针SOT23电流模式升压转换器&#xff0c;低功耗应用。SDB2F5交换机位于1.2MHz&#xff0c;并允许使用高度小于或等于2mm的微小、低成本电容器和电感器。内部软启动的结果在小浪涌电流和延长电池寿命。 该SDB2F5操作从一个…

【15-聚类分析入门:使用Scikit-learn进行K-means聚类】

文章目录 前言K-means聚类的原理Scikit-learn中的K-means实现安装与导入生成模拟数据应用K-means聚类可视化聚类结果选择K的值总结前言 聚类分析是一种无监督学习方法,用于将数据集中的样本分组成若干个簇(cluster)。K-means是最广泛使用的聚类算法之一,其核心思想是将数据点…

爱普生RX8111CE工厂流水线控制模块实现超长待机

经过多年的高速发展&#xff0c;我国已基本实现工业机械化&#xff0c;但距离工业自动化还有很大差距。随着机器人、工业自动化趋势愈演愈烈&#xff0c;未来发展前景日趋明朗。工厂流水线的要求也日益增加&#xff0c;其中包括对计件、计时等定量的要求&#xff0c;还有对设备…

【算法每日一练】

蛮有意思的的一道题&#xff0c;最后要判断能否成为一种1~n的全排列&#xff0c;我最这样做的&#xff1a; 整个数组先排序一下。假设遍历到了i&#xff0c;那就判断前面b和r的个数&#xff0c;但是有想到了后面可能还会对前面的结果产生影响&#xff0c;所以就抛弃了这个想法…

Now in Android 4月份更新速览

Now in Android 4月份更新速览 1. 引言 Android 15 Beta的发布标志着Android生态系统的新一轮更新。这次更新旨在提升用户体验和开发效率&#xff0c;让我们一起来了解其中的重要内容。 2. Android 15 Beta介绍 Android 15 Beta带来了一系列新功能&#xff0c;其中包括默认边…

JAVA同城服务美容美发到店服务上门服务系统源码微信小程序+微信公众号+H5+APP

随着科技的飞速发展&#xff0c;互联网和移动互联网已经渗透到我们生活的方方面面&#xff0c;同城服务美容美发到店服务上门服务系统应运而生&#xff0c;为整个行业带来了巨大的变革和无限的可能。该系统的重要性和优势不言而喻&#xff0c;对于行业发展和用户需求的影响深远…

文件系统学习

软连接&#xff1a;可以跨不同的磁盘块&#xff0c;创建出不同的inode节点 应连接&#xff1a;相同的inode节点&#xff0c;不同的文件名字记录在父亲节点目录中 分区(fdisk)&#xff0c;格式化(mkfs)&#xff0c;挂载(mount)&#xff0c;大于2T分区&#xff08;parted&#…

Go常用的标准库——fmt,time

一.fmt fmt包实现了类似C语言printf和scanf的格式化I/O。主要分为向外输出内容和获取输入内容两大部分。 1.1 向外输出 标准库fmt提供了以下几种输出相关函数。 Print Print系列函数会将内容输出到系统的标准输出&#xff0c;区别在于Print函数直接输出内容&#xff0c;没有换…

【数据结构】二叉树-堆

一、树概念及结构 1.1树的概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限节点组成的一个具有层次的关系的集合。 注意&#xff1a;子树不能相交 节点的度&#xff1a;一个节点含有的子树个数称为该节点的度&#xff1b;A为6&#x…

Elasticsearch 索引的分片和副本是什么意思,如何扩展分片

文章目录 前言Elasticsearch 索引的分片和副本是什么意思&#xff0c;如何扩展分片示例:1. 设置 5个分片&#xff0c;每个分片一个副本的命令2. 将5个分片扩展到10个分片 前言 如果您觉得有用的话&#xff0c;记得给博主点个赞&#xff0c;评论&#xff0c;收藏一键三连啊&…

LabVIEW航空发动机主轴承试验器数据采集与监测

LabVIEW航空发动机主轴承试验器数据采集与监测 随着航空技术的迅速发展&#xff0c;对航空发动机性能的测试与监测提出了更高的要求。传统的数据采集与监测方法已难以满足当前高精度和高可靠性的需求&#xff0c;特别是在主轴承试验方面。基于LabVIEW的航空发动机主轴承试验器…

Linux|awk 特殊模式“BEGIN 和 END”

引言 在本文[1]&#xff0c;我们将介绍Awk的更多特性&#xff0c;特别是两个特殊的模式&#xff1a;BEGIN和END。 这些独特的功能在我们努力扩展和深入探索构建复杂Awk操作的多种方法时&#xff0c;将大有裨益。 实例 让我们从Awk系列的开篇回顾开始&#xff0c;回想一下&#…

指纹浏览器:网络安全与隐私的新工具

在互联网时代&#xff0c;隐私和网络安全成为人们越来越关注的话题。随着数字化的发展&#xff0c;个人信息的泄露和在线追踪的问题愈发严峻。在这个背景下&#xff0c;"指纹浏览器"作为一种新型工具&#xff0c;开始受到关注。撸空投需要了解指纹浏览器。本文将深入…

【启明智显技术分享】关于RS485自动收发电路的问题整理

*【编者按】*随着信息技术的飞速发展&#xff0c;芯片作为现代电子设备的核心组成部分&#xff0c;其应用领域的拓展与性能的提升都成为了业界关注的焦点。在芯片应用过程中&#xff0c;各位小伙伴可能会遇到各种各样的问题。“RS485自动收发电路”作为芯片应用中的一项关键技术…

Prometheus+Grafana多方位监控

PrometheusGrafana多方位监控 契机 ⚙ 最近发现火山引擎有托管的Prometheus,可是当前是邀测阶段。并且发现火山云的ECS是自带开机自启的exporter的。刚好需要搭建一套服务器监控&#xff0c;所以研究了一套Prometheus监控&#xff0c;包含linux主机监控nginx监控es监控rabbitM…

Python俄罗斯方块

文章目录 游戏实现思路1. 游戏元素的定义2. 游戏区域和状态的定义3. 游戏逻辑的实现4. 游戏界面的绘制5. 游戏事件的处理6. 游戏循环7. 完整实现代码 游戏实现思路 这个游戏的实现思路主要分为以下几个步骤&#xff1a; 1. 游戏元素的定义 Brick类&#xff1a;表示游戏中的砖…

CSS样式特异性5层次详解

你好&#xff0c;我是云桃桃。 一个希望帮助更多朋友快速入门 WEB 前端的程序媛。 云桃桃-大专生&#xff0c;一枚程序媛&#xff0c;感谢关注。回复 “前端基础题”&#xff0c;可免费获得前端基础 100 题汇总&#xff0c;回复 “前端工具”&#xff0c;可获取 Web 开发工具合…

云端芳华、运维之美

今天&#xff0c;在我们享受互联网服务带来的便利与高效的同时&#xff0c;有一群人默默地在幕后为我们提供支持&#xff0c;他们就是云端运维人员。 值此五一国际劳动节来临之际&#xff0c;我们要真诚感谢他们辛勤的劳动和奉献&#xff01;

基于ssm+vue开放式教学评价管理系统【ppt·代码·文档报告】

项目演示视频 项目名称&#xff1a;开放式教学评价管理系统 系统介绍&#xff1a;本系统是通过java的SSM框架来实现的&#xff0c;前端采用vue框架进行实现 管理员通过登录进入到系统操作界面&#xff0c;结合需求可以对个人信息进行在线修改维护&#xff0c;也可结合需求进行…

经典文献阅读之--SurroundOcc(自动驾驶的环视三维占据栅格预测)

0. 简介 环视BEV已经是很多场景中需要的功能&#xff0c;也是视觉代替激光雷达的有效解决方案&#xff0c;而《SurroundOcc: Multi-camera 3D Occupancy Prediction for Autonomous Driving》一吻则代表了这个领域的SOTA算法&#xff0c;文中通过多帧点云构建了稠密占据栅格数据…