這次國賽選了B題，雖然拉了但是在做的程序中有一些小理解，想在這里分享出來，

• 對于求解最優序列的問題，序列中的每一個位置的點有自己的狀態，最優序列即為求得最優的狀態序列，這涉及三部分內容：

  1. 定義狀態
  2. 定義狀態的分數
  3. 定義狀態轉移

• 定義狀態： 把一個點的狀態抽象為一個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維的維度，這里不知道說的對不對，希望大佬指正

• 可以拓展到各種優化演算法上，遺傳、蟻群等等感覺都差不多，只是定義狀態的分數和轉移有一點不同，但感覺殊途同歸，