这次国赛选了B题，虽然拉了但是在做的过程中有一些小理解，想在这里分享出来。
-
对于求解最优序列的问题，序列中的每一个位置的点有自己的状态，最优序列即为求得最优的状态序列，这涉及三部分内容：
- 定义状态
- 定义状态的分数
- 定义状态转移
-
定义状态： 把一个点的状态抽象为一个k维向量 ( x 1 , x 2 , . . . , x k ) (x_1,x_2,...,x_k) (x1,x2,...,xk)，该向量的每一维度都代表该状态的不同维度，这些维度的取值合在一起构成了这个内容的状态；
需要注意的是，任何一个状态都有其最基础的一个维度：时间维度，这个时间也可以理解为其在状态序列中的位置；
以B题第一关为例，向量有四个维度分别是时间，玩家位置，玩家消耗的水，玩家消耗的食物，基础维度时间即代表该玩家是在沙漠上的第几天。每一个维度都有不同取值，代表了不同的状态。 -
定义状态的分数： 即为每一个状态 x = ( x 1 , x 2 , . . . , x k ) x = (x_1,x_2,...,x_k) x=(x1,x2,...,xk)维护一个分数 ω \omega ω，分数高代表这个状态更优，记 f ( x ) = x . ω f(x) = x.\omega f(x)=x.ω；
值得注意的是，每一个状态的分数都与其前序状态密切相关；以B题第一关为例，这个 ω \omega ω就是该状态下玩家剩余的资金，其与玩家前一天剩余的资金密切相关。 -
定义状态转移： 首先，定义当前状态 x c x_c xc， x c ∈ ( c , ∗ , ∗ , . . . , ∗ ) x_c \in (c,*,*,...,*) xc∈(c,∗,∗,...,∗)， c ∈ 0 , 1 , 2 , . . . , T c \in {0,1,2,...,T} c∈0,1,2,...,T，那么有 x c + 1 = N e x t ( x c ) x_{c+1} = Next(x_c) xc+1=Next(xc)，其中 N e x t ( x c ) Next(x_c) Next(xc)代表 x c x_c xc的下一个状态
假设 x c + 1 = ( x 1 ′ , x 2 ′ , . . . , x k ′ ) x_{c+1} = (x_1',x_2',...,x_k') xc+1=(x1′,x2′,...,xk′)，考虑 ∃ x c ′ ≠ x c \exists x_c' \neq x_c ∃xc′=xc，并且 N e x t ( x c ′ ) = x c + 1 Next(x_c') = x_{c+1} Next(xc′)=xc+1，这便是子问题之间的重复性，带有这个特征的问题可以使用动态规划算法求解：
即令 x c ˉ = { x c ∣ x c ∈ ( c , ∗ , ∗ , . . . , ∗ ) ∧ N e x t ( x c ) = x c + 1 } \bar{x_c} = \{x_c| x_c \in (c,*,*,...,*) \wedge Next(x_c) = x_{c+1}\} xcˉ={ xc∣xc∈(c,∗,∗,...,∗)∧Next(xc)=xc+1}，那么有 x c + 1 = a r g m a x ( f ( x c ˉ ) + C o s t ( x c → x c + 1 ) ) (*) x_{c+1} = argmax(f(\bar{x_c}) + Cost(x_c \rightarrow x_{c+1})) \tag{*} xc+1=argmax(f(xcˉ)+Cost(xc→xc+1))(*)其中 C o s t ( x c → x c + 1 ) Cost(x_c \rightarrow x_{c+1}) Cost(xc→xc+1)代表从 x c x_c xc转移到 x c + 1 x_{c+1} xc+1带来的分数变化，每一个分数不同的 x c x_c xc都可能转移到分数不同的 x c + 1 x_{c+1} xc+1，即
f ( x c ) + C o s t ( x c → x c + 1 ) = f ( x c + 1 ) f(x_c) + Cost(x_c \rightarrow x_{c+1}) = f(x_{c+1}) f(xc)+Cost(xc→xc+1)=f(xc+1)
因此， ( ∗ ) (*) (∗)式可以转化为
x c + 1 = a r g m a x ( f ( x c + 1 ˉ ) ) x_{c+1} = argmax(f(\bar{x_{c+1}})) xc+1=argmax(f(xc+1ˉ))
其中 x c + 1 ˉ = N e x t ( x c ˉ ) \bar{x_{c+1}} = Next(\bar{x_c}) xc+1ˉ=Next(xcˉ)， a r g m a x ( ω ) argmax(\omega) argmax(ω)代表选出 ω \omega ω最大的 x c x_c xc
之后重复上述转移过程，每一个 x c x_c xc都会是具有最高分数的，即最优的，最后有
x T = a r g m a x ( f ( x T ˉ ) ) x_{T} = argmax(f(\bar{x_{T}})) xT=argmax(f(xTˉ))
x T x_{T} xT即为序列的最终位置的最优状态，根据此状态回溯其前序状态，则可以得到序列中每一个位置的最优状态与其转移。 -
动态规划是用于求解会有状态重合的时候的算法，可以把 O ( D 2 ∗ D 3 ∗ . . . ∗ D k ) T O(D_2 * D_3 *...*D_k)^T O(D2∗D3∗...∗Dk)T的复杂度降低到 O ( D 2 ∗ D 3 ∗ . . . ∗ T ) O(D_2 * D_3 * ... *T) O(D2∗D3∗...∗T)，其中 D i D_i Di是 x x x中第 i + 1 i+1 i+1维的维度，这里不知道说的对不对，希望大佬指正
-
可以拓展到各种优化算法上，遗传、蚁群等等感觉都差不多，只是定义状态的分数和转移有一点不同，但感觉殊途同归。
