Acwing-基础算法课笔记之动态规划(计数类DP)

Acwing-基础算法课笔记之动态规划(计数类DP)

  • 一、整数划分
    • 1、定义
    • 2、完全背包的做法
      • 代码示例
      • (1)过程模拟
      • (2)代码示例
    • 3、计数类DP的做法
      • (1)过程模拟
      • (2)闫氏DP分析法
      • (3)代码示例

一、整数划分

1、定义

一个正整数 n可以表示成若干个正整数之和,形如:
n = n 1 + n 2 + . . . + n k n=n_1+n_2+...+n_k n=n1+n2+...+nk,其中 n 1 ≥ n 2 ≥ . . . ≥ n k , k ≥ 1 n_1\ge n_2\ge...\ge n_k,k\ge1 n1n2...nk,k1

举例:
假设要将 5 5 5划分,以下是划分的情况:
5 = 5 5=5 5=5
5 = 1 + 4 5=1+4 5=1+4
5 = 2 + 3 5=2+3 5=2+3
5 = 1 + 1 + 3 5=1+1+3 5=1+1+3
5 = 1 + 2 + 2 5=1+2+2 5=1+2+2
5 = 1 + 1 + 1 + 2 5=1+1+1+2 5=1+1+1+2
5 = 1 + 1 + 1 + 1 + 1 5=1+1+1+1+1 5=1+1+1+1+1

2、完全背包的做法

状态表示:
d p [ i ] [ j ] dp[i][j] dp[i][j]表示只从 1 ∼ i 1\sim i 1i中选,且总和等于 j j j的方案数

状态转移方程:
f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − i ] f[i][j]=f[i-1][j]+f[i][j-i] f[i][j]=f[i1][j]+f[i][ji]
其中 f [ i − 1 ] [ j ] f[i-1][j] f[i1][j]指的是当物品装不进背包时,前 i − 1 i-1 i1个物品当中最大价值, f [ i ] [ j − i ] f[i][j-i] f[i][ji]指的是装的下的情况。(此为个人理解,如果有不对的地方请纠正错误)

代码示例

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int dp[N];
int mod = 1e9 + 7;
int main() {
	scanf("%d", &n);
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			dp[j] = (dp[j] + dp[j - i]) % mod;
		}
	}
	printf("%d", dp[n]);
	return 0;
}

(1)过程模拟

012345
0100000
1111111
2102233
3100345
4100056
5100007

上表中,列表示的是最终和的值,行表示和值最多由 j j j个数相加, d p [ i ] [ j ] dp[i][j] dp[i][j]则是表示的是方案个数。

(2)代码示例

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int dp[N];
int mod = 1e9 + 7;
int main() {
	scanf("%d", &n);
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			dp[j] = (dp[j] + dp[j - i]) % mod;
		}
	}
	printf("%d", dp[n]);
	return 0;
}

3、计数类DP的做法

(1)过程模拟

012345
0100000
1010000
2011000
3011100
4012110
5012211

上表中,列表示的是总和 i i i,行表示有 j j j个数相加, d p [ i ] [ j ] dp[i][j] dp[i][j]则是表示的是有 j j j个数相加构成 i i i的数量。

(2)闫氏DP分析法

在这里插入图片描述

(3)代码示例

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int dp[N][N];
int mod = 1e9 + 7;
int main() {
	scanf("%d", &n);
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % mod;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)ans = (ans + dp[n][i]) % mod;
	printf("%d", ans);
	return 0;
}

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

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

相关文章

页面侧边栏顶部固定和底部固定方法

顶部固定用于侧边栏低于屏幕高度----左侧边栏 底部固定用于侧边栏高于屏幕高度----右侧边栏 vue页面方法 页面布局 页面样式&#xff0c;因为内容比较多&#xff0c; 只展示主要代码 * {margin: 0;padding: 0;text-align: center; } .head {width: 100%;height: 88px;back…

Language models scale reliably with over-training and on downstream tasks

Language models scale reliably with over-training and on downstream tasks 相关链接&#xff1a;arxiv 关键字&#xff1a;语言模型、过度训练、下游任务、可扩展性、性能预测 摘要 本文探讨了语言模型在过度训练和下游任务中的可扩展性。尽管现有的扩展研究通常集中在计算…

【Linux】基础 IO(文件描述符)-- 详解

一、前言 1、文件的宏观理解 文件在哪呢&#xff1f; 从广义上理解&#xff0c;键盘、显示器、网卡、声卡、显卡、磁盘等几乎所有的外设都可以称之为文件&#xff0c;因为 “Linux 下&#xff0c;一切皆文件”。 从狭义上的理解&#xff0c;文件在磁盘&#xff08;硬件&#…

虚拟机 VMware下载及安装

centos官网&#xff1a;CentOS Mirror 虚拟机vmware官网&#xff1a;VMware 官网 一直点下一步就好了&#xff0c;有些配置按需修改即可 创建新的虚拟机 处理内核总数不能大于自己主机的逻辑处理器 安装操作系统&#xff1a;引入centos镜像 然后就可以点击开启此虚拟机&#xf…

软考76-上午题-【面向对象技术3-设计模式】-创建型设计模式01

一、创建型设计模式一览 二、创建型设计模式 2-1、创建型设计模式的概念 一个类创建型模式使用继承改变被实例化的类&#xff1b; 一个对象创建型模式将实例化委托给另一个对象。 对应java的new一个对象。 2-2、简单工厂模式&#xff08;静态工厂方法&#xff09; 简单工厂…

Python电梯楼层数字识别

程序示例精选 Python电梯楼层数字识别 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对《Python电梯楼层数字识别》编写代码&#xff0c;代码整洁&#xff0c;规则&#xff0c;易读。 学习与应…

第四篇 - 环境:移动设备、台式设备和联网电视 - IAB视频广告标准《数字视频和有线电视广告格式指南》

第四篇 - 环境&#xff1a;移动设备、台式设备和联网电视 - IAB视频广告标准《数字视频和有线电视广告格式指南》 --- 我为什么要翻译介绍美国人工智能科技公司IAB系列技术标准&#xff08;2&#xff09; ​​​​​​​翻译计划 第一篇序言第二篇简介和目录第三篇概述- IAB…

linux解析域名指令 nslookup 或者 host

host www.baidu.com 第二种方法 nslookup www.baidu.com 注意&#xff1a;ns是name server之意

纯 CSS 实现文字换行环绕效果

实现效果 实现代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>Document</title><…

前端学习之css样式 背景样式、字体样式、列表样式、边框样式、内外边距元素属性的转换

背景样式 html文件 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>背景样式</title><link rel"stylesheet" href"../css/3.1背景样式.css"> </head> <bo…

基于springboot+vue实现员工信息管理系统项目【项目源码+论文说明】

基于springbootvue实现员工信息管理系统演示 引言 随着计算机技术的飞速发展&#xff0c;计算机在企业管理中应用的普及&#xff0c;利用计算机在实现企业人事档案的管理势在必行。当今社会正快速向信息化社会前进&#xff0c;信息自动化的作用也越来越大。从而使我们从繁杂的…

蓝桥杯第 6 场 小白入门赛 2.猜灯谜(for + 数组)

思路&#xff1a;注意是环形排列的灯笼&#xff0c;它的谜底是相邻两个灯笼的数字之和。这道题要用到两个数组&#xff0c;ans存答案&#xff0c;a存原数据。数据读入部分就不用说了&#xff0c;重点就是单独写明ans[0]和ans[n-1]两个取值&#xff0c;其他的用for循环数组就可以…

【Linux】进程与可执行程序的关系fork创建子进程写实拷贝的理解

一、进程与可执行程序之间关系的理解 系统会将此时在系统运行的进程的各种属性都以文件的形式给你保存在系统的proc目录下。运行一个程序的时候&#xff0c;本质就是把磁盘中的程序拷贝到内存中&#xff0c;当一个进程运行起来的时候&#xff0c;它本质已经和磁盘中的可执行程序…

Python分析两个数据集车辆轨迹的相似度

项目背景 最近遇到这样一个需求&#xff1a; 有两个数据集&#xff0c;radar1.radar4.csv&#xff0c;这两个数据集是由位置相邻的两个雷达记录&#xff0c;且这两个雷达的检测区域有部分重合&#xff0c;两个数据集的字段有deviceId ptcType ptcId source timestamp longitud…

重学SpringBoot3-ServletWebServerFactoryAutoConfiguration类

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 重学SpringBoot3-ServletWebServerFactoryAutoConfiguration类 工作原理关键组件以TomcatServletWebServerFactory为例ServletWebServerFactory会创建webServer的时机关键…

数据结构与算法-树-二分搜索树(一)

二分搜索树 今天我们尝试构建一颗二分搜索树&#xff0c;很多同学只有理论&#xff0c;并没有对树有其编码实践。通过一步步的实现一颗二分搜索树&#xff0c;加深对数据结构树的理解。 二分搜索树&#xff0c;又名二分排序树&#xff0c;有人也叫它二分查找树。 特点 二分搜索…

Python爬虫与数据可视化源码免费领取

引言 作为一名在软件技术领域深耕多年的专业人士&#xff0c;我不仅在软件开发和项目部署方面积累了丰富的实践经验&#xff0c;更以卓越的技术实力获得了&#x1f3c5;30项软件著作权证书的殊荣。这些成就不仅是对我的技术专长的肯定&#xff0c;也是对我的创新精神和专业承诺…

腾讯云2核2G免费服务器申请流程,2024免费服务器入口

腾讯云免费服务器申请入口 https://curl.qcloud.com/FJhqoVDP 免费服务器可选轻量应用服务器和云服务器CVM&#xff0c;轻量配置可选2核2G3M、2核8G7M和4核8G12M&#xff0c;CVM云服务器可选2核2G3M和2核4G3M配置&#xff0c;腾讯云服务器网txyfwq.com分享2024年最新腾讯云免费…

深度学习 精选笔记(13.2)深度卷积神经网络-AlexNet模型

学习参考&#xff1a; 动手学深度学习2.0Deep-Learning-with-TensorFlow-bookpytorchlightning ①如有冒犯、请联系侵删。 ②已写完的笔记文章会不定时一直修订修改(删、改、增)&#xff0c;以达到集多方教程的精华于一文的目的。 ③非常推荐上面&#xff08;学习参考&#x…

【C++刷题】优选算法——动态规划第一辑

1.状态表示是什么&#xff1f;简答理解是dp表里的值所表示的含义怎么来的&#xff1f;题目要求经验题目要求分析问题的过程中&#xff0c;发现重复子问题 2.状态转移方程dp[i]......细节问题&#xff1a;3.初始化控制填表的时候不越界4.填表顺序控制在填写当前状态的时候&#…
最新文章