数据结构与算法-动态规划-状态机（股票问题，密码设计）
状态机概念
状态机模型（Finite - State Machine，FSM）也叫有限状态自动机，是一种抽象的计算模型，在计算机科学、电子工程等众多领域有广泛应用，以下从定义、组成部分、类型、应用场景等方面介绍：
定义
状态机是表示有限个状态以及在这些状态之间转移和动作等行为的数学模型。它能根据当前所处状态和输入的信号，决定后续的状态转移和相应输出。
组成部分
状态集合（States）：包含所有可能的状态，比如在交通信号灯状态机中，可能有红灯、绿灯、黄灯等状态。
输入集合（Inputs）：能被状态机接收的所有输入信号，例如交通信号灯状态机中，可能的输入有定时时间结束、行人按钮按下等。
转移函数（Transition Function）：根据当前状态和输入，决定下一个状态的规则。比如交通信号灯在绿灯状态下，定时时间结束这个输入发生时，转移到黄灯状态。
初始状态（Initial State）：状态机开始运行时所处的状态，如交通信号灯默认从红灯状态开始。
输出函数（Output Function）：基于当前状态或状态转移产生相应输出，像交通信号灯状态改变时，控制灯泡亮起不同颜色。
类型
摩尔型状态机（Moore Machine）：输出仅取决于当前状态，与输入信号直接无关。例如一个简单的计数器状态机，状态表示计数值，输出是当前计数值，只由当前所处计数值状态决定。
米利型状态机（Mealy Machine）：输出同时取决于当前状态和输入信号。比如在一个密码验证状态机中，输出是否验证成功，既和当前处于验证的哪个阶段（状态）有关，也和当前输入的密码字符有关。
动态规划中的状态机：
动态规划中的状态机模型是一种借助状态机思想来解决动态规划问题的有效方式，它将问题的求解过程抽象为状态之间的转移
基本概念
把问题的不同阶段和状态变化看作状态机的状态转移，通过定义状态、状态转移方程和初始条件等，利用状态机的运行规则来逐步推导最优解。它能清晰地梳理问题中复杂的状态关系和转移逻辑，帮助解决具有多阶段决策特点的问题。
关键要素
状态定义：明确状态机中的各个状态，这些状态要能完整且准确地描述问题在不同阶段的特征。例如在股票买卖问题中，可能定义 “未持有股票”“已持有股票” 等状态。
状态转移：确定从一个状态到另一个状态的条件和方式。比如在上述股票问题中，“未持有股票” 状态在买入股票时可转移到 “已持有股票” 状态。
状态转移方程：用数学表达式描述状态之间的转移关系以及对应的值的变化，这是动态规划求解的核心。例如设(dp[i][j])表示第(i)天处于状态(j)时的最大收益，通过分析不同状态转移情况得到转移方程来计算最大收益。
初始状态和边界条件：确定状态机开始时的状态以及一些特殊情况的处理方式。如在股票买卖开始时，“未持有股票” 状态下收益为(0) 。
应用步骤
分析问题并确定状态：剖析问题的阶段和状态特征，找出能描述问题的合理状态集合。
定义状态转移规则：根据问题的逻辑和条件，确定状态之间的转移条件和方式。
构建状态转移方程：基于状态和转移规则，写出计算不同状态下最优值的方程。
设定初始状态和边界条件：为状态机的运行提供起始条件和特殊情况的处理依据。
按顺序计算状态值：按照问题的阶段顺序，依据状态转移方程逐步计算每个状态的值，最终得到最优解。
典型示例（下面包括了2个不同的状态：持有股票：1,和未持有股票：0）
以股票买卖问题为例，限制交易次数为(k)次，可定义以下状态：
(dp[i][j][0])：第(i)天，已经进行了(j)次交易，当前未持有股票时的最大收益。
(dp[i][j][1])：第(i)天，已经进行了(j)次交易，当前持有股票时的最大收益。
状态转移方程如：
(dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])) （不持有股票的状态可能由前一天不持有或前一天持有且当天卖出转移而来）
(dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])) （持有股票的状态可能由前一天持有或前一天不持有且当天买入转移而来）
通过设定初始状态（如(dp[0][0][0]=0)，(dp[0][0][1]= -prices[0])等），按顺序计算这些状态值，就能得出在给定交易次数限制下的最大收益。
引例：
分析
我们的子问题f[i][j]表示，经过前i个店铺，j为0,表示不抢第i个,1表示抢第i个的最大收益
转移的分析如下：
状态转移方程是：
伪代码如下：
因为第i个的状态只和i-1有关，所以可以使用滚动数组
习题1（2状态的状态机）
分析：
这是一道经典的股票交易收益最大化问题，属于动态规划领域的常见题型。
给定一个长度为 (N) 的数组，数组中每个元素代表一只股票在对应天数的价格，即第 (i) 个数字表示该股票在第 (i) 天的价格。
设计算法计算在最多可完成 (k) 笔交易的限制下，能够获取的最大利润。同时明确交易规则为不能同时参与多笔交易，每次买入和卖出合为一笔交易，且必须在再次购买前出售掉之前持有的股票。
该问题的难点在于如何在满足交易次数限制和交易规则的前提下，通过合理安排买卖时机来实现利润最大化。通常需要运用动态规划思想，定义合适的状态（如不同天数、不同交易次数、持有或不持有股票等状态），并推导状态转移方程来求解。
子问题f[i][j][k]表示的是前i天，通过j次交易获得的收益，k为1表示持有股票，k为0表示没持有股票
状态转移：
再看转移的具体的形式：
注意：f[0][j][1/0]都是不合法的方案，因为第0天不可能进行过交易，也不可能持有股票，所以初始化的时候最好都初始化为-INF
状态转移方程和伪代码如下：
习题2（3状态的状态机）
分析：
给定一个长度为 \(N\) 的数组，数组中第 \(i\) 个数字代表某只股票在第 \(i\) 天的价格。
设计算法计算在特定约束条件下的最大利润，并且要尽可能完成更多交易。
交易互斥：不能同时参与多笔交易，即每次买入前必须先卖出之前持有的股票。
冷冻期规则：卖出股票后，第二天无法买入股票，存在一天的冷冻期。
解决本题需综合考虑股票价格变化、交易次数以及冷冻期限制，通常可运用动态规划的方法，通过定义合适的状态（如持有股票、不持有股票且处于冷冻期、不持有股票且不处于冷冻期等状态），推导状态转移方程来求解最大利润。
状态机分析：有三个状态，转移关系如下·
转移方程;
使用滚动数组优化后的代码：
习题3（m状态的状态机）
分析：
对于一个子串abc，他有4个状态，分别是 ‘’,’a',’ab’,’abc’我们根据这个状态的特性来设计算法，这个题目就要求我们设计的密码不能包含最后的一个状态就可以了。
假设一个字符串有m个字符，第i个字符在j的状态，它的下一个状态是什么和第i+1个字符有关，如果第i+1个字符和我们的T串中的下一个字符一致，那么会进入第j+1个状态，否则就会进入之前的状态，具体是哪一个状态，这个就可以用kmp的思想来解决了（不一定是直接回到起点的，比如aabaab,在最后一个点转移失败了，应该回到下标为2的点继续向后比较）
对于每个点的下一个状态只有26个可能（a~z），所以我们可以先把这个状态转移的图给构建起来，然后再去进行设计
下面是一个我们假定的状态转移图，我们假设我们在第j个状态，那么下一个字符有26个可能，加入下一个是’c’,那么我们就可能转移到第j+1个状态,也可能下一个字符是’a’导致我们转移到第0个状态,显然我们都可以通过预处理将0-m-1个状态的下一个字符的26个可能到达的状态都计算出来,这样就完成了我们的建图工作
状态转移就如下面的公式一样,我们当前的f[i][j]表示i个字符达到了j的状态，那么我们下一个转移到的状态就是f[i+1][x]，这里的x就是我们上面建图得知的26个可能的状态之一。
f[i+1][x]=f[i+1][x]+f[i][j]
伪代码如下：
