加载中...

地址发布 老王说明书 宣传中心
此板块只作为纯讨论

正经话题,不搞色情!贤者时间必备
查看: 975|回复: 14
收起左侧

[学习讨论] 求助大佬,有没有那种快速做出状态转移方程的方法

[复制链接]
 楼主| 发表于 2023-10-22 22:16:45 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?免费注册

x
每次刷Leetcode和luogu碰到DP的题就完全没思路。。。" ^: m' x/ E& e) T! c0 ]( w(欢迎访问老王论坛:laowang.vip)
2 g! P2 Z% o$ i; K! N(欢迎访问老王论坛:laowang.vip)
顺便吐槽一下:今年CSP-S T3是真出生啊,TM不考算法考大模拟,做到后面直接自闭。。。
; v% e  p" I7 w/ M3 x: f
回复

使用道具 举报

发表于 2023-10-23 00:44:07 | 显示全部楼层

修改修改修改修改

本帖最后由 navebayes 于 2023-10-23 00:47 编辑
. U3 e4 A7 R# [% p  W/ Q- G* h  Q( w/ A/ i5 p# A(欢迎访问老王论坛:laowang.vip)
大部分状态方程都是基于斐波那契和类斐波那契,建议使用你做曾经数学题时的方法,给状态划为代数再去看他;例如,F[n]=max(f[n-1]+u(n),f[n-2]+v(n)) 这是一个最简单的状态转移方程。他的本质就那么简单: 前一个状态F(n-1)进行u处理, 和前前一个状态F(n-2)进行V处理;当图分支为n时,那么就要添加更多状态进行处理比对。  ?9 Q6 g3 \/ h" H! e2 H(欢迎访问老王论坛:laowang.vip)
. @  Y8 q3 e2 D& H(欢迎访问老王论坛:laowang.vip)
也就是这个泛抽象公式:  MAX/MIN/equal ( [状态A和他的前进条件],[状态B和他的前进条件]  )
1 ]8 P" u  x5 u" r3 u/ X
4 x3 {0 D7 d* q. U, C% R/ B例如这样一道题,87. 扰乱字符串 如果用dfs做 他的状态转移方程就是 ( f4 f1 D# P3 A" x- }! h% \(欢迎访问老王论坛:laowang.vip)
F[m][n]=存在 Equal{F[m]+F[n],F[n]+F[m]}   (具体很烦的嘞...又需要对段检查,又需要一段段咔过去 试着写了一部分写不下去了)/ ^8 D9 m5 j6 l1 E(欢迎访问老王论坛:laowang.vip)
" j# C: H0 k5 ?(欢迎访问老王论坛:laowang.vip)

3 w" \1 y* g4 m$ W% L8 R- ^( y) I记住,一切优化都是建立在可以暴力解题且有余力的情况下,答题时无脑优化只会拖慢节奏1 _; T/ t# d2 X' ~/ w/ B& o(欢迎访问老王论坛:laowang.vip)
(这个应该是dp公式吧 。。很久没刷了)
回复 支持 6 反对 0

使用道具 举报

发表于 2023-10-23 13:01:58 手机版 | 显示全部楼层
大家不会都是研究生,就我一个本科毕业了就当社畜吧
回复 支持 2 反对 0

使用道具 举报

发表于 2023-10-23 10:08:33 | 显示全部楼层
论坛真是人才济济啊,看得我不明觉厉
回复 支持 2 反对 0

使用道具 举报

发表于 2023-10-23 10:20:59 | 显示全部楼层
状态转移方程...我以为是自动控制原理的那种呢
回复 支持 反对

使用道具 举报

发表于 2023-10-23 12:00:01 手机版 | 显示全部楼层
urk32 发表于 2023-10-23 10:204 I2 Y. R) U% r" y) F6 `. F9 b(欢迎访问老王论坛:laowang.vip)
状态转移方程...我以为是自动控制原理的那种呢
' \- l* B" k: _(欢迎访问老王论坛:laowang.vip)
那个是自动机(. ❛ ᴗ ❛.)自动机的状态转移一般不是用方程的。虽然差距其实也不大,只不过这个更局部一些
回复 支持 反对

使用道具 举报

发表于 2023-10-23 13:53:09 | 显示全部楼层
navebayes 发表于 2023-10-23 12:00' T1 F6 j( \! k! h1 r(欢迎访问老王论坛:laowang.vip)
那个是自动机(. ❛ ᴗ ❛.)自动机的状态转移一般不是用方程的。虽然差距其实也不大,只不过这个更局部一 ...

7 x- ~6 y' T) E( n. W! G/ \7 _* s哈哈 [现代控制理论1-2] 状态方程的标准形式与解 - 知乎 (zhihu.com) 学过这种& s) h2 H$ p* ^(欢迎访问老王论坛:laowang.vip)

评分

参与人数 1软妹币 +100 收起 理由
navebayes + 100 小心不要掉回1了

查看全部评分

回复 支持 反对

使用道具 举报

发表于 2023-10-23 14:26:36 手机版 | 显示全部楼层
urk32 发表于 2023-10-23 13:53. L7 P+ W# a8 F" T) n) o. j(欢迎访问老王论坛:laowang.vip)
哈哈 [现代控制理论1-2] 状态方程的标准形式与解 - 知乎 (zhihu.com) 学过这种  T, ~6 i0 v, F; k) ?+ n(欢迎访问老王论坛:laowang.vip)
...
- c4 D, Z5 M8 D2 R& F(欢迎访问老王论坛:laowang.vip)
原来说的是这个呀,我没有学过⊙︿⊙莫名联想到范畴,改天研究一下这个
回复 支持 反对

使用道具 举报

发表于 2023-10-23 23:13:43 手机版 | 显示全部楼层
zzzq|abstract 发表于 2023-10-23 13:01
  h% P4 L! q" E( f, G大家不会都是研究生,就我一个本科毕业了就当社畜吧
) V/ z7 T+ V5 U9 R: L(欢迎访问老王论坛:laowang.vip)
(T_T)
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-10-30 21:56:57 | 显示全部楼层
hikari4512 发表于 2023-10-23 10:08  H( ], s1 M7 j: j9 H/ W(欢迎访问老王论坛:laowang.vip)
论坛真是人才济济啊,看得我不明觉厉
: N! o8 D$ e+ |6 _- [/ A7 J(欢迎访问老王论坛:laowang.vip)
我才初二(8 h- Z3 b1 f/ R/ R, E0 m' b(欢迎访问老王论坛:laowang.vip)
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-10-30 21:59:47 | 显示全部楼层
navebayes 发表于 2023-10-23 00:44
; W1 g+ `# R2 R, K- S/ N3 I大部分状态方程都是基于斐波那契和类斐波那契,建议使用你做曾经数学题时的方法,给状态划为代数再去看他; ...
1 O2 `$ @  ]2 l3 [(欢迎访问老王论坛:laowang.vip)
Orz,最近在刷Luogu上DP的题单,您的回答对我帮助很大(
9 `# {. o/ J# J4 Q
回复 支持 反对

使用道具 举报

发表于 2023-10-30 22:36:26 | 显示全部楼层
gaogao0621 发表于 2023-10-30 21:591 e9 G0 H/ C$ `% w(欢迎访问老王论坛:laowang.vip)
Orz,最近在刷Luogu上DP的题单,您的回答对我帮助很大(
' A+ P* r" p3 X- V3 W(欢迎访问老王论坛:laowang.vip)
能帮到你就行 才初二吗?确实是一个比较次时代的ioer的年龄。不过我接下来的建议可能有些浇你冷水3 y8 m, I& Q* w; ]% s) C: n(欢迎访问老王论坛:laowang.vip)

8 d: h, I' n: R- Z  X! e算法的本质是用逻辑的方式解决问题,大部分程序爱好者往往会纠结于某些语言,或者某些固定的‘算法类型’。但他们背后实际都可以是数学的另一种表示。赛博世界的黑客很强大,这和那个世界完善的基础信息建设离不开关系。算法,编程之类的也一样,也只是逻辑的拼接 思维的碰撞(最重要的逻辑就是数学的思维,逻辑)。我希望你不会沉迷算法里,虽然他们很酷。但如果你没有足够的学识和上升的条件,那也只能止步于很酷而已;别抛下日常的学习。5 v. r- b: i% Y4 n' t3 _  j(欢迎访问老王论坛:laowang.vip)

. p  O4 D1 X" t3 N
, _3 P: d" }6 }- U8 ^0 {8 F7 t嗯..拿个比较合适的例子来说吧。例如 卷积视觉算法认数字,一般这个是被作为人工智能学习的入门来做;但如果你使用算法的思维很难地去想‘如何认出数字’的话,这是比较困难的。不过当你的基础数学能力扎实,且能理解线性代数与概率论之类更“高级”的数学工具时,你就可以明白:$ G8 @6 I0 S3 {6 M- |1 o' K  q- f(欢迎访问老王论坛:laowang.vip)
哦,我可以让每一个片段都通过抽象压缩的卷积核把9个点变成一个,以此进行猜测寻找。例如9和1,九的形状在中间有色的概率小而1在中间有色的概率大。
: h8 X7 B, }; [2 r* |5 K. e1 O" W7 g( L) ]: w(欢迎访问老王论坛:laowang.vip)
说这些主要是看到前段时间一个贴子,有一个成绩很差的初中生发帖表示自己想走数竞考大学,理由就是 他学会的微积分。 微积分在普通人眼中确实是很高大上的东西,但微积分学的本质就是数学工具,那个初中生也只是会用这些数学工具解决问题而已。让他解决更复杂的问题?但他的基础的数学逻辑能力跟不上啊..
8 ^8 K+ O! }  [' T+ v9 u+ j- S" w# x+ x: j/ L% P! X3 @(欢迎访问老王论坛:laowang.vip)

. j0 R; D- |; Y6 g0 E( [' ?4 L. H! f0 t' n& S/ @(欢迎访问老王论坛:laowang.vip)
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-10-30 22:48:47 | 显示全部楼层
navebayes 发表于 2023-10-30 22:36
8 E) @) j# J/ |* E能帮到你就行 才初二吗?确实是一个比较次时代的ioer的年龄。不过我接下来的建议可能有些浇你冷 ...

# _$ b  w/ N0 P. A确实,毕竟这个信息学竞赛只是爱好,常规的文化课还是没有落下的。感谢大佬让我意识到我之前直接学概率论,集合论这些是完全没有用的,应该从我目前的知识水平一步一步学到那里(" t/ z2 b7 t! _+ f4 L& ?* D(欢迎访问老王论坛:laowang.vip)
7 l7 V! Y9 S: I1 p- T(欢迎访问老王论坛:laowang.vip)
回复 支持 反对

使用道具 举报

发表于 2023-10-30 22:52:23 | 显示全部楼层
gaogao0621 发表于 2023-10-30 22:48, v! y9 o. _: c  t# `$ w3 z" w(欢迎访问老王论坛:laowang.vip)
确实,毕竟这个信息学竞赛只是爱好,常规的文化课还是没有落下的。感谢大佬让我意识到我之前直接学概率论 ...
- W& z, X8 ]/ d9 Q. {6 @& T* l8 Y(欢迎访问老王论坛:laowang.vip)
我不是大佬啦..那些是有用,但不是现在。现在你直接理解他们的成本很高,这会拖慢你现在的学习进度的。
; l* m: u% n# p4 [& t
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 免费注册
点击进行验证

本版积分规则

我们不生产资源,只做资源的搬运工。

tags标签-春满四合院-AvGood-Archiver-小黑屋- |网站地图