当前位置：首页 > news >正文

一道经典的整数划分题——分弹珠

news 来源：原创 2025/7/17 17:34:24

CSDN 博客：一道经典的整数划分题——分弹珠

一、题目描述

这道题目是一道经典的整数划分问题，要求将 (M) 个弹珠分到 (N) 个盘子中，满足以下条件：

允许盘子为空。
两种分法被认为相同当且仅当分配的弹珠数量相同（不考虑顺序）。

例如，将 (7) 个弹珠分到 (3) 个盘子中的方法数是 (8)。如果不考虑盘子顺序，分法包括：
$(7, 0, 0), (6, 1, 0), (5, 2, 0), (5, 1, 1), (4, 3, 0), (4, 2, 1), (3, 3, 1), (3, 2, 2) 。$

二、整数划分题的核心思想

整数划分是组合数学中的经典问题。整数划分问题的核心在于：

如果我们用 $P (m, n)$ 表示将 $m$ 个物品分到 $n$ 个容器中的分法数，那么可以利用递推关系解决问题。

递推公式推导

考虑将 $M$ 个弹珠分到 $N$ 个盘子中：

如果我们规定 盘子 $N$ 为空，那么问题就转化为将 $M$ 个弹珠分到 $N - 1$ 个盘子中，即 $P (m, n - 1)$ 。
如果盘子 $N$ 不为空，我们至少需要放一个弹珠，那么问题就转化为将剩下的 $M - N$ 个弹珠分到 $N$ 个盘子中，即 $P (m - n, n)$ 。

因此，递推公式为：
$P (m, n) = P (m, n - 1) + P (m - n, n),$
同时考虑到边界条件：

当 (m = 0) 时，只有一种分法，即所有盘子均为空：
$P (0, n) = 1$
当 (n = 0) 且 (m > 0) 时，分法数为 (0)：
$P (m, 0) = 0$
当 (n > m) 时，盘子的数量大于弹珠数量，此时最多只需 (m) 个盘子，因此：
$P (m, n) = P (m, m)$

三、两种解法详解

方法一：带备忘录的递归

带备忘录的递归利用了记忆化搜索的思想，可以避免重复计算。代码如下：

#include <iostream>
#include <cstring>
using namespace std;int memo[21][21]; // 备忘录，用于存储中间结果// 递归计算 P(m, n)
int P(int m, int n) {if (m == 0) return 1;          // 边界条件：0个弹珠只有1种分法if (m < 0 || n == 0) return 0; // 边界条件：盘子用完或弹珠数量负数if (n > m) return P(m, m);     // 若盘子数多于弹珠数，限制盘子数为mif (memo[m][n] != -1) return memo[m][n]; // 如果已计算过，直接返回结果memo[m][n] = P(m, n-1) + P(m-n, n); // 递推公式return memo[m][n];
}int main() {memset(memo, -1, sizeof(memo)); // 初始化备忘录int t, M, N;while (cin >> t) {for (int i = 0; i < t; i++) {cin >> M >> N;cout << P(M, N) << endl;}}return 0;
}

解法分析

时间复杂度：由于每个状态 $P (m, n)$ 只计算一次，总的复杂度为 $\times N)$ 。
空间复杂度：需要额外的 $\times N)$ 空间存储中间结果。

方法二：分治法（动态规划）

动态规划通过表格存储所有子问题的解，从而避免了递归调用的开销。代码如下：

#include <iostream>
using namespace std;int dp[21][21]; // 动态规划数组// 初始化动态规划表
void initialize_dp() {for (int m = 0; m <= 20; m++) {for (int n = 0; n <= 20; n++) {if (m == 0)dp[m][n] = 1; // 边界条件else if (n == 0)dp[m][n] = 0; // 边界条件else if (n > m)dp[m][n] = dp[m][m]; // 当盘子数多于弹珠数elsedp[m][n] = dp[m][n-1] + dp[m-n][n]; // 递推公式}}
}int main() {initialize_dp(); // 初始化 DP 表int t, M, N;while (cin >> t) {for (int i = 0; i < t; i++) {cin >> M >> N;cout << dp[M][N] << endl;}}return 0;
}

解法分析

时间复杂度：预处理的复杂度为 $\times N)$ ，查询的复杂度为 $O (1)$ 。
空间复杂度：需要 $\times N)$ 的存储空间。

四、总结

本题作为整数划分问题的典型代表，考察了递归与动态规划的灵活运用：

递归方法（带备忘录）更容易直观理解，但需要注意栈的深度。
动态规划方法 是实际中更高效且稳定的选择，特别是在多组测试的情况下。

整数划分的核心在于掌握 递推公式 的推导，并灵活运用 边界条件 简化问题的求解。希望本篇博客能够帮助读者对整数划分问题有更深入的理解！

一道经典的整数划分题——分弹珠

CSDN 博客：一道经典的整数划分题——分弹珠一、题目描述这道题目是一道经典的整数划分问题，要求将 (M) 个弹珠分到 (N) 个盘子中，满足以下条件： 允许盘子为空。两种分法被认为相同当且仅当分配的弹珠数量相同（不考…...

编程日记 2025/7/17 17:34:24

浏览器缓存与协商缓存

1. 强缓存（Strong Cache） 定义强缓存是指在缓存的资源有效期内，浏览器会直接使用缓存中的数据，而不会发起网络请求。也就是说，浏览器会直接从本地缓存读取资源，不会与服务器进行任何交互。如何控制强缓…...

编程日记 2025/7/17 17:32:46

Maven 如何配置忽略单元测试

在使用 Maven 进行项目构建时，有时您可能希望跳过测试阶段。这在确保代码更改不影响测试结果或需要快速部署项目的情况下特别有用。 Maven 提供了多种方法来在构建过程中跳过测试。为什么跳过测试？ 加速构建：对于具有大量测试用例的大项…...

编程日记 2025/7/14 18:52:02

哪里能找到好用的动物视频素材优质网站推荐

想让你的短视频增添些活泼生动的动物元素？无论是搞笑的宠物瞬间，还是野外猛兽的雄姿，这些素材都能让视频更具吸引力。今天就为大家推荐几个超实用的动物视频素材网站，不论你是短视频新手还是老手，都能在这些网站找到心…...

编程日记 2025/7/13 22:21:16

Python中的23种设计模式：详细分类与总结

设计模式是解决特定问题的通用方法，分为创建型模式、结构型模式和行为型模式三大类。以下是对每种模式的详细介绍，包括其核心思想、应用场景和优缺点。一、创建型模式（Creational Patterns） 创建型模式关注对象的创建&#xff0…...

编程日记 2025/7/15 13:42:30

研0找实习【学nlp】14--BERT理解

以后做项目，一定要多调查，选用不同组合关键词多搜索！ BERT论文解读及情感分类实战_bert模型在imdb分类上的准确率已经到达了多少的水平-CSDN博客【深度学习】-Imdb数据集情感分析之模型对比（4）- CNN-LSTM…...

编程日记 2025/7/12 23:31:09

【AI日记】24.11.27 学习 kaggle 入门比赛 Titanic - Machine Learning from Disaster

【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】【AI日记】核心工作内容：学习 kaggle 入门比赛 Titanic - Machine Learning from Disaster时间：8 小时心得：在学习别人的 notebook 的时候，碰到不懂的知识点，…...

编程日记 2025/7/15 19:22:39

HCIP——堆叠技术实验配置

目录一、堆叠的理论知识二、堆叠技术实验配置三、总结一、堆叠的理论知识 1.1堆叠概述： 是指将两台交换机通过堆叠线缆连接在一起，从逻辑上变成一台交换设备，作为一个整体参与数据的转发。 1.2堆叠的基本概念堆叠系统中所有的单台…...

编程日记 2025/7/16 17:52:40

trtllm 部署新体验

实验清华大模型和trtllm Chatglm3 pip3 install tensorrt_llm -U --pre --extra-index-url https://pypi.nvidia.com 要安装git来下载仓库使用这个chatglm的例子安装依赖用最新的glm3的model 然后开始转换model 官方写错了，这应该是个-，不是_&a…...

编程日记 2025/7/16 8:02:28

部署 DeepSpeed以推理 defog/sqlcoder-70b-alpha 模型

部署 DeepSpeed 以推理 defog/sqlcoder-70b-alpha 这样的 70B 模型是一个复杂的过程，涉及多个关键步骤。下面是详细的步骤，涵盖了从模型加载、内存优化到加速推理的全过程。 1. 准备环境确保你的环境配置正确，以便能够顺利部署 defog/sqlc…...

编程日记 2025/7/12 9:13:04

node.js基础学习-http模块-创建HTTP服务器、客户端（一）

http模块式Node.js内置的模块，用于创建和管理HTTP服务器。Node.js使用JavaScript实现，因此性能更好。使用http模块创建服务器，我们建议使用commonjs模块规范，因为很多第三方的组件都使用了这种规范。当然es6写法也支持。下面就是…...

编程日记 2025/7/12 14:56:50

Cobalt Strike 4.8 用户指南-第十一节 C2扩展

11.1、概述 Beacon 的 HTTP 指标由 Malleable Command and Control （Malleable C2） 配置文件控制。Malleable C2 配置文件是一个简单的程序，它指定如何转换数据并将其存储在事务中。转换和存储数据的同一程序（向后解释&#xff0…...

编程日记 2025/6/30 13:37:05

STM32 使用ARM Compiler V6 编译裸机 LWIP协议栈报错的解决方法

在lwip 的cc.h 中使用以下宏定义，来兼容 V5 和 V6编译器 #if defined (__ARMCC_VERSION) && (__ARMCC_VERSION > 6010050) /* ARM Compiler V6 */ #define __CC_ARM /* when use v6 compiler define this */ #endifV6编译的速度确实比V5块了好多倍。 …...

编程日记 2025/7/2 22:31:36

K8S简介、使用教程

以下是关于 Kubernetes（通常缩写为 K8S）的简介和使用教程： 一、Kubernetes 简介定义与作用 Kubernetes 是一个开源的容器编排平台，用于自动化部署、扩展和管理容器化应用程序。它最初由谷歌开发，后捐赠给云原生计算基…...

编程日记 2025/7/14 1:36:20

Scala—Map用法详解

Scala—Map用法详解在 Scala 中，Map 是一种键值对的集合，其中每个键都是唯一的。Scala 提供了两种类型的 Map：不可变 Map 和可变 Map。 1. 不可变集合（Map） 不可变 Map 是默认的 Map 实现，位于 scala.co…...

编程日记 2025/7/16 10:15:13

2024御网杯信息安全大赛个人赛wp（misc方向）

目录一.信息安全大赛的通知二、编码转换1. 第一部分2. 第二部分3. 第三部分三、1.txt四、buletooth 题目附件以及工具链接： 通过网盘分享的文件：御网杯附件链接: https://pan.baidu.com/s/1LNA6Xz6eZodSV0Io9jGSZg 提取码: jay1 –来自百度网盘超级会…...

编程日记 2025/7/16 16:13:44

DeepSpeed 配置文件（DeepSpeed Configuration Files）详解：中英文解释

中文版本文详细介绍 DeepSpeed 配置文件，结合 4 卡 3090 的实际使用场景，重点解释各个参数的含义，并提供应对爆显存的方案。 DeepSpeed 配置文件详解：从基础到实战 DeepSpeed 是用于加速大规模分布式训练的重要工具&#xff0c…...

编程日记 2025/7/16 20:11:20

AI 助力开发新篇章：云开发 Copilot 深度体验与技术解析

本文一、引言：技术浪潮中的个人视角1.1 AI 和低代码的崛起1.2 为什么选择云开发 Copilot？ 二、云开发 Copilot 的核心功能解析2.1 自然语言驱动的低代码开发2.1.1 自然语言输入示例2.1.2 代码生成的模块化支持 2.2 实时预览与调整2.2.1 实时预览窗口功能…...

编程日记 2025/7/15 8:52:36

QTableWidget使用代理绘制分行显示

在这里插入代码片# 创建主窗口类： 使用 QTableWidget 作为核心控件。设置表头及行列信息。自定义代理： 继承 QStyledItemDelegate，实现代理模式。重写 paint 和 sizeHint 方法，支持多行文本绘制。设置行高以适应多行显示。 …...

编程日记 2025/7/16 8:33:01

Linux系统之fuser命令的基本使用

Linux系统之fuser命令的基本使用一、fuser命令介绍二、fuser命令使用帮助2.1 help帮助信息2.1 基本语法①通用选项②文件/设备相关选项③网络相关选项④进程操作选项⑤其他选项三、fuser命令的基本使用3.1 查找挂载点的进程3.2 查看指定设备进程信息3.3 查找监听特定端口的进…...

编程日记 2025/7/15 19:04:17

解决`-bash: ./configure：/bin/sh^M：解释器错误: 没有那个文件或目录`的问题

解决`-bash: ./configure：/bin/sh^M：解释器错误: 没有那个文件或目录`的问题一、错误原因分析二、解决方法方法一：使用`dos2unix`工具方法二：使用`sed`命令方法三：使用`tr`命令方法四：在文本编辑器中转换方法五：在Windows系统中使用适当的工具三、预防措施四、总结在使…...

编程日记 2025/7/15 22:09:49

【时时三省】(C语言基础)结构体的声明

山不在高，有仙则名。水不在深，有龙则灵。 ----CSDN 时时三省结构的基础知识结构是一些值的集合，这些值称为成员变量。结构的每个成员可以是不同类型的变量。数组是一组相同类型的元素的集合结构体也是一些值的集合，结构的每…...

编程日记 2025/7/12 17:31:26

群聊前选择患者功能的实现

和普通群聊不同，开启一个图文会话聊天，必须先选择患者、团队、医生。原来是集成到腾讯IM当中，现在需要单独写一个页面原来的代码在这里： const handleShow () > {uni.navigateTo({url: /pageB/active-home/active-home})}…...

编程日记 2025/7/16 17:52:58

目标检测，图像分割，超分辨率重建

目标检测和图像分割目标检测和图像分割是计算机视觉中的两个不同任务，它们的输出形式也有所不同。下面我将分别介绍这两个任务的输出。图像分割又可以分为：语义分割、实例分割、全景分割。语义分割（Semantic Segmentation）&…...

编程日记 2025/7/17 1:10:09

关于 EKS Bottlerocket AMI 版本与 Karpenter 配置的说明

问题1: Bottlerocket AMI 版本问题之前,后端团队发现在使用 Bottlerocket v1.26.2 AMI 版本时,存在某些问题。经过 Bottlerocket 团队调查,此行为是罕见的 race condition 导致的结果。我们在环境中重现了此状况,并且关注到由于 kubelet device manager 的启动时间晚于 NVI…...

编程日记 2025/7/12 22:43:24

安全设备-日志审计-网络路由配置

1 网络设置菜单项‘网络’‘网络设置’子项。进入网卡列表展示页面。点击操作列‘编辑’图标，可编辑对应网卡信息。图11-1 网卡信息设备接口的 GE0/1 接口IP:192.168.0.1子网掩码:255.255.255.0 图11-2 配置网卡 1 IP地址2 子网掩码3 主机DNS4 备份DNS 2 通…...

编程日记 2025/7/15 10:30:01

Linux服务器生成SSH 密钥对与 GitLab 仓库进行交互

目录生成 SSH 密钥对将公钥添加到 GitLab 测试 SSH 连接生成 SSH 密钥对在执行脚本的机器上打开终端，执行以下命令（假设使用默认的 RSA 算法，一路回车使用默认设置即可，也可以根据需要指定其他算法和参数）&…...

编程日记 2025/7/16 4:46:15

react 的路由功能

1. 安装依赖 pnpm add react-router-dom 2. 基本的路由设置（BrowserRouter） 在 main.tsx 入口文件中使用BrowserRouter组件来包裹整个应用。它会监听浏览器的 URL 变化。 import { StrictMode } from "react";import { createRoot } from …...

编程日记 2025/7/12 21:09:58

vscode python code runner执行乱码

打开vscode code runner插件配置，如图所示： 然后在setting.json修改运行python的默认命令： 将原来替换成 "python":"set PYTHONIOENCODINGutf8 && python", 参考：Vscode——python环境输出中文乱…...

编程日记 2025/7/15 18:52:40

Element UI 打包探索【3】

目录第九个命令 node build/bin/gen-cssfile gulp build --gulpfile packages/theme-chalk/gulpfile.js cp-cli packages/theme-chalk/lib lib/theme-chalk 至此，dist命令完成。解释why Element UI 打包探索【1】里面的why Element UI 打包探索【2】里面…...

编程日记 2025/7/16 13:20:07

windows使用docker安装centos7

参考文章：docker容器安装CentOS7.9 需要指出来的步骤 2.5 安装常用工具及ssh服务由于centos7不维护，需要更换镜像源才能正常使用yum install命令安装更换镜像源文章：CentOS 7配置yum镜像源 2.9Xshell远程连接docke_centos7.9 文章没有指…...

编程日记 2025/7/17 4:15:54

写一个流程，前面的圆点和线，第一个圆上面没有线，最后一个圆下面没有线

上图最近写类似于这种的还挺多的，记录一下css方法遍历列表之后 <div class"item" v-for"(item,index) in recordList"> 加这样一个盒子 <div class"timeline"> <div class"line1" v-if"index ! 0&…...

编程日记 2025/7/14 9:32:15

Javascript Insights: Visualizing Var, Let, And Const In 2024

11/2024 出版 MP4 |视频：h264， 19201080 |音频：AAC，44.1 KHz 语言：英语 |大小： 2.96 GB |时长： 5 小时 34 分钟为所有认真的 JavaScript 开发人员可视化与 VAR、LET、CONST 和 EXECUTON CONTE…...

编程日记 2025/7/14 10:34:55

【工具】AI 工具集整理推荐

ai工具集我私人使用了一段时间，效果不错，有很多AI工具，可以提升工作的效率。...

编程日记 2025/7/3 15:33:40

如何通过终端连接无线网

1 先连接对方服务器 ssh root192.168.3.219　# root是用户名字　192.168.3.219是对方的ip地址2 开启 WiFi：输入sudo nmcli r wifi on，开启系统的无线网络功能 sudo nmcli r wifi on3　扫描附近的 WiFi 热点：执行sudo nmcli dev wifi&#x…...

编程日记 2025/7/16 19:02:48

elasticsearch报错fully-formed single-node cluster with cluster UUID

1.问题描述 k8s集群内部署的es中间件起不来，查看日志发现如下警告，节点发现功能开启，但是目前我是单节点服务，所以尝试编辑sts将节点发现功能去掉或者在部署时将你的sts的yaml文件和chart文件修改重新部署以去掉该功能 {"t…...

编程日记 2025/7/9 17:23:52

前端 vue3 + element-plus + ts 对话框示例

【父组件】：SampleInput.vue，局部代码片段引入子组件 ApplyItemChooseDialog.vue，定义变量，用于渲染和显示标识 <script>片段代码 import ApplyItemChooseDialog from "/views/accept/ApplyItemChooseDialog.vue&q…...

编程日记 2025/7/14 13:00:08

南京移动“智慧+关怀”服务体系助力老年群体生活安全有保障

在数字化浪潮汹涌澎湃的当下，江苏移动南京分公司秉持“人民邮电为人民”的服务理念，推出一系列创新服务举措，为社区老年群体提供贴心、便捷的数字服务，让老人在享受科技发展成果的同时，感受到社会的温暖与关怀。贴心…...

编程日记 2025/7/16 9:16:25

Elasticsearch 安全特性讲解与使用

Elasticsearch安全特性讲解与使用指南 1. Elasticsearch概览1.1 简介1.2 应用场景1.3 核心特性2. Elasticsearch安全特性2.1 安全性的重要性2.2 权限控制用户身份验证角色管理访问控制列表(ACL)2.3 数据加密数据传输加密数据静态加密2.4 审计日志2.5 IP筛选2.6 案例分析案例背景…...

编程日记 2025/7/13 1:13:39

第12章手写Spring MVC

第十二章手写Spring MVC 12.1 基本结构搭建 12.1.1 创建Maven模块 12.1.2 引入Servlet依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XM…...

编程日记 2025/7/13 20:07:48

C#基础31-35

31.已知学生的记录由学号和学习成绩构成，N名学生的数据已存入student数组中。找出成绩最低的学生记录(假定最低成绩的记录是唯一的)并输出。 32.在键盘上任意输入一个字符串，该字符串全部由英文字母组成，把字符串中的最后一个字符的ASCII值右移4位后加最后第二个字符的ASCII…...

编程日记 2025/7/13 1:33:11

GPT相关的学术库——收藏更新自用

GOT-OCR2.0 General OCR Theory: Towards OCR-2.0 via a Unified End-to-end Model https://github.com/Ucas-HaoranWei/GOT-OCR2.0/tree/main ChatPaper 工具名称工具作用是否在线？在线预览备注ChatPaper通过ChatGPT实现对论文进行总结，帮助科研人进…...

编程日记 2025/7/14 19:03:20

速度革命：esbuild如何改变前端构建游戏 (1)

什么是 esbuild？ esbuild 是一款基于 Go 语言开发的 JavaScript 构建打包工具，以其卓越的性能著称。相比传统的构建工具（如 Webpack），esbuild 在打包速度上有着显著的优势，能够将打包速度提升 10 到 100 倍…...

编程日记 2025/7/13 11:51:46

AR商业化的“AI转身”

AI会不会是AR厂商良药？ 作者|周立青编辑|杨舟 11月，国内“AR四小龙”之一的Rokid举办了新品发布会，在发布会的同步直播间，出现了一条不合时宜的“什么时候发去年的工资”的评论。 “公司确实没有给我们发2023年的十三薪和年终…...

编程日记 2025/7/16 5:16:56

Python 中的装饰器是什么？

装饰器是Python中一种非常强大的功能，它允许你在不修改原始函数代码的前提下，增加额外的功能或改变函数的行为。装饰器本质上是一个接受函数作为参数的函数，并返回一个新的函数。通过装饰器，我们可以轻松地实现诸如日志记录、…...

编程日记 2025/7/16 5:14:38

jupyter notebook的 markdown相关技巧

目录 1 先选择为markdown类型 2 开关技巧 2.1 运行markdown 2.2 退出markdown显示效果 2.3 注意点：一定要先选择为markdown类型 3 一些设置技巧 3.1 数学公式 3.2 制表 3.3 目录和列表 3.4 设置各种字体效果：加粗，斜体&#x…...

编程日记 2025/7/16 22:24:56

oracle 创建只可以查询权限用户+sqldeveloper如何看到对应表

声明申明部分是从其他csdn用户哪里复制的，只是自己操作后发现无法达到我最后的预期，所以关闭忘记是看的那篇了，如果有侵权请见谅，联系我删除谢谢。好了，故事的开始是我最近删投产表了。没错职业黑点，清…...

编程日记 2025/7/13 19:12:24

化工行业 FMEA 与安全生产的关系

【大家好，我是唐Sun，唐Sun的唐，唐Sun的Sun。】在化工行业这个充满复杂性和潜在危险的领域中，确保安全生产是至关重要的目标。失效模式及影响分析（FMEA）作为一种有效的风险管理工具，在保障化工行…...

编程日记 2025/7/17 14:01:32

前端node.js

一.什么是node.js 官网解释:Node.js 是一个开源的、跨平台的 JavaScript 运行时环境。二.初步使用node.js 需要区分开的是node.js和javascript互通的只有console和定时器两个API. 三.Buffer Buffer 是一个类似于数组的对象，用于表示固定长度的字节序列。Buffer…...

编程日记 2025/7/15 11:18:02

深度学习：GPT-2的MindSpore实践

GPT-2简介 GPT-2是一个由OpenAI于2019年提出的自回归语言模型。与GPT-1相比，仍基于Transformer Decoder架构，但是做出了一定改进。模型规格上： GPT-1有117M参数，为下游微调任务提供预训练模型。 GPT-2显著增加了模型规模&…...

编程日记 2025/7/12 15:43:53

CSDN 博客：一道经典的整数划分题——分弹珠

一、题目描述

二、整数划分题的核心思想

递推公式推导

三、两种解法详解

解法分析

解法分析

四、总结

相关文章：