求助大佬，有没有那种快速做出状态转移方程的方法

gaogao0621

每次刷Leetcode和luogu碰到DP的题就完全没思路。。。

# j9 Y! U% |6 J0 K% W3 K# g' i顺便吐槽一下：今年CSP-S T3是真出生啊，TM不考算法考大模拟，做到后面直接自闭。。。

navebayes

+ s/ Y1 E; a* C4 H( f
( R' {1 z5 O/ ]! T大部分状态方程都是基于斐波那契和类斐波那契，建议使用你做曾经数学题时的方法，给状态划为代数再去看他；例如，F[n]=max(f[n-1]+u(n),f[n-2]+v(n)） 这是一个最简单的状态转移方程。他的本质就那么简单： 前一个状态F（n-1）进行u处理， 和前前一个状态F（n-2）进行V处理；当图分支为n时，那么就要添加更多状态进行处理比对。
9 \; j1 s6 E4 W7 q6 r
/ T: w. f+ M. J也就是这个泛抽象公式：  MAX/MIN/equal （ [状态A和他的前进条件]，[状态B和他的前进条件]  ）

3 k" [2 _; q: r0 \6 {( a* W& t例如这样一道题，87. 扰乱字符串 如果用dfs做 他的状态转移方程就是
* x' `" m! ?2 @2 V1 k; r$ [6 [F[m][n]=存在 Equal{F[m]+F[n],F[n]+F[m]}   （具体很烦的嘞...又需要对段检查，又需要一段段咔过去 试着写了一部分写不下去了）


$ k" F% _0 [* C6 W4 J! Z记住，一切优化都是建立在可以暴力解题且有余力的情况下，答题时无脑优化只会拖慢节奏
（这个应该是dp公式吧 。。很久没刷了）

zzzq|abstract

大家不会都是研究生，就我一个本科毕业了就当社畜吧

hikari4512

论坛真是人才济济啊，看得我不明觉厉

urk32

状态转移方程...我以为是自动控制原理的那种呢

navebayes

urk32 发表于 2023-10-23 10:20
状态转移方程...我以为是自动控制原理的那种呢

那个是自动机(. ❛ ᴗ ❛.)自动机的状态转移一般不是用方程的。虽然差距其实也不大，只不过这个更局部一些

urk32

navebayes 发表于 2023-10-23 12:00
% U, O0 v( E: o那个是自动机(. ❛ ᴗ ❛.)自动机的状态转移一般不是用方程的。虽然差距其实也不大，只不过这个更局部一 ...

5 M2 |6 h  x! y; c) @# Q7 k哈哈 [现代控制理论1-2] 状态方程的标准形式与解 - 知乎 (zhihu.com) 学过这种

navebayes

urk32 发表于 2023-10-23 13:53
) d  @5 A% ~8 J0 v1 q2 ^哈哈 [现代控制理论1-2] 状态方程的标准形式与解 - 知乎 (zhihu.com) 学过这种
. ]' U6 h3 m4 w! _+ T) r& A( _ ...

" }; o: B8 F) F8 R. t. p6 a原来说的是这个呀，我没有学过⊙︿⊙莫名联想到范畴，改天研究一下这个

navebayes

zzzq|abstract 发表于 2023-10-23 13:01
大家不会都是研究生，就我一个本科毕业了就当社畜吧

) U) j- X% Q; F  F3 y2 A% S(T＿T)

gaogao0621

hikari4512 发表于 2023-10-23 10:08
) U& K! l6 K* i论坛真是人才济济啊，看得我不明觉厉

( V8 ]; C& M$ [; j& h1 d5 o( L& E* x我才初二（

gaogao0621

navebayes 发表于 2023-10-23 00:44
( i% h6 G$ I- a# W9 o7 ~大部分状态方程都是基于斐波那契和类斐波那契，建议使用你做曾经数学题时的方法，给状态划为代数再去看他； ...

1 [) P( }5 F4 [# z. y5 `Orz，最近在刷Luogu上DP的题单，您的回答对我帮助很大（

navebayes

gaogao0621 发表于 2023-10-30 21:59
Orz，最近在刷Luogu上DP的题单，您的回答对我帮助很大（

+ O. ?& P+ J  j* c  Q* H能帮到你就行 才初二吗？确实是一个比较次时代的ioer的年龄。不过我接下来的建议可能有些浇你冷水
/ `/ l2 M4 o- ~; E; D
0 l1 {* F$ T9 }算法的本质是用逻辑的方式解决问题，大部分程序爱好者往往会纠结于某些语言，或者某些固定的‘算法类型’。但他们背后实际都可以是数学的另一种表示。赛博世界的黑客很强大，这和那个世界完善的基础信息建设离不开关系。算法，编程之类的也一样，也只是逻辑的拼接 思维的碰撞（最重要的逻辑就是数学的思维，逻辑）。我希望你不会沉迷算法里，虽然他们很酷。但如果你没有足够的学识和上升的条件，那也只能止步于很酷而已；别抛下日常的学习。
  ^( Y6 _7 d* J" l# K9 j( e) o1 I! S( O
; t! t, G8 d0 w. }+ y- y. d
嗯..拿个比较合适的例子来说吧。例如 卷积视觉算法认数字，一般这个是被作为人工智能学习的入门来做；但如果你使用算法的思维很难地去想‘如何认出数字’的话，这是比较困难的。不过当你的基础数学能力扎实，且能理解线性代数与概率论之类更“高级”的数学工具时，你就可以明白：
6 V+ o5 M, [1 z6 B0 f哦，我可以让每一个片段都通过抽象压缩的卷积核把9个点变成一个，以此进行猜测寻找。例如9和1，九的形状在中间有色的概率小而1在中间有色的概率大。
0 M  n* I! N+ `5 u
& _) `4 ?: a9 L- N; A; P: N说这些主要是看到前段时间一个贴子，有一个成绩很差的初中生发帖表示自己想走数竞考大学，理由就是 他学会的微积分。 微积分在普通人眼中确实是很高大上的东西，但微积分学的本质就是数学工具，那个初中生也只是会用这些数学工具解决问题而已。让他解决更复杂的问题？但他的基础的数学逻辑能力跟不上啊..
/ l/ m; }" h6 l! s- W' x# @( x
" B2 f! {) U( K6 @) D" g( s0 ?# c2 a
  d/ z, p: h* N2 P( f9 _5 y
6 f/ I# B/ Q' i" R8 Y. n% X

gaogao0621

navebayes 发表于 2023-10-30 22:36
2 s  y9 G2 R. W7 u( r9 J+ Y9 c6 z能帮到你就行 才初二吗？确实是一个比较次时代的ioer的年龄。不过我接下来的建议可能有些浇你冷 ...

7 M  z5 i0 y; ?3 S( ]6 c3 O确实，毕竟这个信息学竞赛只是爱好，常规的文化课还是没有落下的。感谢大佬让我意识到我之前直接学概率论，集合论这些是完全没有用的，应该从我目前的知识水平一步一步学到那里（
8 Q7 E3 n4 ?! t: R4 T+ w) O# W( Q
4 h  z' d+ p: p" K. l  e0 K5 ]9 N( ^, W

navebayes

gaogao0621 发表于 2023-10-30 22:48
5 V  \. i( R4 O3 e7 m9 y) o确实，毕竟这个信息学竞赛只是爱好，常规的文化课还是没有落下的。感谢大佬让我意识到我之前直接学概率论 ...

我不是大佬啦..那些是有用，但不是现在。现在你直接理解他们的成本很高，这会拖慢你现在的学习进度的。