搜索
查看
编辑修改
首页
UNITY
NODEJS
PYTHON
AI
GIT
PHP
GO
CEF3
JAVA
HTML
CSS
搜索
小惠珠哦
这个屌丝很懒,什么也没留下!
关注作者
热门标签
jquery
HTML
CSS
PHP
ASP
PYTHON
GO
AI
C
C++
C#
PHOTOSHOP
UNITY
iOS
android
vue
xml
爬虫
SEO
LINUX
WINDOWS
JAVA
MFC
CEF3
CAD
NODEJS
GIT
Pyppeteer
article
热门文章
1
阿里 P7 到底是怎样的水平?_阿里p7年薪
2
回答 | 开源项目有哪些机遇与挑战?
3
如何避免推荐系统中的雪崩效应?
4
新闻文本分类任务:使用Transformer实现_transformer文本分类
5
javascript高级程序设计
6
Mysql - 索引
7
Librechat快速部署指南
8
渗透测试面试问题,内含大量渗透技巧_渗透测试面经
9
前端uniapp开源盲盒源码后端php tp6框架H5+小程序+app_uniapp源码
10
基于Python+django电影影片数据爬取与数据分析系统 大屏可视化
当前位置:
article
> 正文
动态规划(dp) 之 状态转移方程_dp的状态转移方程
作者:小惠珠哦 | 2024-07-23 16:07:30
赞
踩
dp的状态转移方程
-----机器分配问题
F[I,j]:=max(f[i-1,k]+w[i,j-k])
2. 资源问题2
------01背包问题
F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);
3. 线性动态规划1
-----朴素最长非降子序列
F[i]:=max{f[j]+1}
4. 剖分问题1
-----石子合并
F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);
5. 剖分问题2
-----多边形剖分
F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]);
6. 剖分问题3
------乘积最大
f[i,j]:=max(f[k,j-1]*mult[k,i]);
7. 树型动态规划1
-----加分二叉树 (从两侧到根结点模型)
F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]}
8. 递推天地2
------数的划分
f[i,j]:=f[i-j,j]+f[i-1,j-1];
9. 线型动态规划3
-----最长公共子串,LCS问题
f[i,j]={0 (i=0)&(j=0);
f[i-1,j-1]+1 (i>0,j>0,x[i]=y[j]);
max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x[i]<>y[j]);
10. 资源问题4
-----装箱问题(判定性01背包)
f[j]:=(f[j] or f[j-v[i]]);
11. 数字三角形1
-----朴素の数字三角形
f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);
12. 双向动态规划1
数字三角形3
-----小胖办证
f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])
13. 数字三角形4
-----过河卒
//边界初始化
f[i,j]:=f[i-1,j]+f[i,j-1];
14. 递推天地3
-----情书抄写员
f[i]:=f[i-1]+k*f[i-2]
15 线性动态规划5
-----隐形的翅膀
min:=min{abs(w[i]/w[j]-gold)};
if w[i]/w[j]<gold then inc(i) else inc(j);
16 最短路1
-----Floyd
f[i,j]:=max(f[i,j],f[i,k]+f[k,j]);
ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];
17 线性动态规划
------合唱队形
两次F[i]:=max{f[j]+1}+枚举中央结点
1. 资源问题1
-----机器分配问题
F[I,j]:=max(f[i-1,k]+w[i,j-k])
2. 资源问题2
------01背包问题
F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);
3. 线性动态规划1
-----朴素最长非降子序列
F[i]:=max{f[j]+1}
4. 剖分问题1
-----石子合并
F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);
5. 剖分问题2
-----多边形剖分
F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]);
6. 剖分问题3
------乘积最大
f[i,j]:=max(f[k,j-1]*mult[k,i]);
7. 树型动态规划1
-----加分二叉树 (从两侧到根结点模型)
F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]}
8. 递推天地2
------数的划分
f[i,j]:=f[i-j,j]+f[i-1,j-1];
9. 线型动态规划3
-----最长公共子串,LCS问题
f[i,j]={0 (i=0)&(j=0);
f[i-1,j-1]+1 (i>0,j>0,x[i]=y[j]);
max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x[i]<>y[j]);
10. 资源问题4
-----装箱问题(判定性01背包)
f[j]:=(f[j] or f[j-v[i]]);
11. 数字三角形1
-----朴素の数字三角形
f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);
12. 双向动态规划1
数字三角形3
-----小胖办证
f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])
13. 数字三角形4
-----过河卒
//边界初始化
f[i,j]:=f[i-1,j]+f[i,j-1];
14. 递推天地3
-----情书抄写员
f[i]:=f[i-1]+k*f[i-2]
15 线性动态规划5
-----隐形的翅膀
min:=min{abs(w[i]/w[j]-gold)};
if w[i]/w[j]<gold then inc(i) else inc(j);
16 最短路1
-----Floyd
f[i,j]:=max(f[i,j],f[i,k]+f[k,j]);
ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];
17 线性动态规划
------合唱队形
两次F[i]:=max{f[j]+1}+枚举中央结点
声明:
本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:
https://www.wpsshop.cn/w/小惠珠哦/article/detail/870592
推荐阅读
article
MYSQL
数据
库基础--MySQL
子
查询
怎么操作?_
mysql
查询
列表
,
一张
主表
一张
子
表
,
一主多
子
,
...
子
查询
有三种使用场景分别是:
子
查询
结果作为判断条件、
子
查询
结果作为枚举条件、
子
查询
结果作为一个虚拟表进行二次
查询
。以上三...
赞
踩
article
java
算法题
Day29
...
每日两练
java
算法题
Day29
...
赞
踩
article
Qwen1.5
原理_qwen1.5
prompt
format
...
使用模型进行微调,主要了解该模型如何构造
prompt
,尤其对单轮对话和多轮对话的处理方式,只有了解并掌握其原理,才能根...
赞
踩
article
大
数据
数仓
基础知识
学习笔记【2】_
全量
,
增量
,
存量
...
数据
仓库(Data Warehouse,DW)
数据
仓库是一个面向主题的、集成的、非易失的且随时间变化的
数据
集合主要用于历...
赞
踩
article
PHP
版
微信
小
程序
商城
源码
和搭建_
微信
小
程序
商城
源码
php
...
PHP
版
微信
小
程序
商城
源码
和搭建_
微信
小
程序
商城
源码
php
微信
小
程序
商城
源码
php
...
赞
踩
article
postgresql 类型转化时遇到的问题_
pgsql
报错
default
for
column
c...
postgres=# alter table test alter config type jsonb;ERROR: c...
赞
踩
article
使用
Python
实现深度学习
模型
:
序列
到
序列
模型
(
Seq2Seq
)_
序列
到
序列
(
seq2seq
)
模型
...
Seq2Seq
模型
通常由两个主要部分组成:编码器(Encoder)和解码器(Decoder)。编码器将输入
序列
编码成一...
赞
踩
article
JVM
高频
基本
面试问题整理_
jvm
面试题
...
JVM
一些
基本
问题的总结分享_
jvm
面试题
jvm
面试题
目录 1.分析
JVM
运行时数据区...
赞
踩
article
vue3
+
threejs
实现全景
看房
_
threejs
vr
看房
...
Threejs全景
看房
_
threejs
vr
看房
threejs
vr
看房
...
赞
踩
article
数字
IC
/
FPGA
设计
_
新人入行分析
_
ic
设计
要学
fpga
么...
数字
IC
/
FPGA
设计
新人入行分析。
_
ic
设计
要学
fpga
么
ic
设计
要学
fpga
么 ...
赞
踩
article
大
数据
学习
技术栈及
书籍
推荐_
大
数据
开发
书籍
...
这种分布式存储和计算的方式使得Hadoop能够处理
大
规模
数据
集,并提供高可靠性和容错性,即使某个节点发生故障,
数据
仍然可...
赞
踩
article
WPF
项目
实战视频《二》
(
主要
为
prism
框架
)...
WPF
视频学习笔记《二》
prism
框架
WPF
项目
实战视频《二》
(
主要
为
prism
框架
) ...
赞
踩
article
IT
岗位
2022届毕业生
简历
制作_根据不同
的
就业
岗位
生成对应
的
简历
csdn
...
简历
制作1.个人信息1.个人信息个人信息是客观存在
的
,必须写以下信息姓名:注意生僻字可以加上拼音学校:专业:如果专业不是...
赞
踩
article
Flink
Sql和
Flink
DataStream
的
区别及使用场景_日常工作中
flink
sql用
的
...
Apache
Flink
是一个强大
的
分布式流处理框架,它提供了两种主要
的
编程 API:
Flink
SQL 和 Flin...
赞
踩
article
分享
57
个
Python
源码,总有一款适合您_
python
办公自动化
源代码
下载
...
分享
57
个
Python
源码,总有一款适合您_
python
办公自动化
源代码
下载
python
办公自动化
源代码
下载
...
赞
踩
article
JS特效第144弹:
audio
古典
的
胶片
音乐
播放器
代码_
audio
+
js
制作
古典
胶片
音乐
播放器
...
经典的JS特效动画效果,效果实现的全部代码、工具、资源已提供,可供学习借鉴_
audio
+
js
制作
古典
胶片
音乐
播放器
aud...
赞
踩
article
Flink
笔记整理
(
三
)
...
DataStream API是
Flink
的核心层API,一个
Flink
程序,其实本质就是对DataStream的各种转换...
赞
踩
article
元
宇宙
行业深度研究报告:
为什么
元
宇宙
是
下一代
互联网
?_
虚拟化
设计并运用到
元
宇宙
平台及其
生态系统
...
目录1、什么是
元
宇宙
?
为什么
元
宇宙
是
下一代
互联网
1.1、
元
宇宙
:
下一代
沉浸式
互联网
1.1.1、超越虚拟与现实的科幻畅想...
赞
踩
article
部署
nas
+
jellyfin
+
阿里
云盘
+内网穿透实现
家庭影院
_
jellyfin
阿里
云盘
...
随着数据量的不断发展,以及目前各种大家懂的原因,将来各种资源互联网会越来越稀缺,对于我们这种影片资源爱好者来说,急需一个...
赞
踩
article
fl
studio
mobile中文汉化包
4.4
.
5
手机版下载_fl
studio
mobile
4.4
....
Hey, Beat Makers! fl
studio
mobile
4.4
.
5
Hey,...
赞
踩
相关标签
数据库
mysql
sql
java
算法
人工智能
深度学习
python
php
开发语言
alter
type
using
jvm
javascript
vue.js
前端
芯片
verilog
fpga
soc
大数据
ambari
clickhouse