笔记_状态转移方程

 

1. 意义，什么是状态转移方程？

状态转移，顾名思义，就是从一个状态迈向另一个状态的过程；一个连续的过程，一个函数的极限，物理的机械决定，天体的运行预测，都是通过上一个状态而影响下一个状态，由上一个状态而决定下一个个状态。

上一个状态与下一个状态不是孤立的，它们是有关联的

而状态转移方程，便是通过类似数列递推的形式去表示这一个过程中的关系，通过依据上一个状态的变化来获得下一个状态。

 

     2.形式，状态转移方程的构建？

在算法编程中，数组是一个构造状态转移方程的好路径。

数组的下标可以抽象为某些状态（第几个操作、第几个节点、第几盆花、哪里哪里有多少东西……），而数组的下标也可以扩展成二维、三维等等维度，同时描述多个变量间的关系。

用多维数组来表示抽象出的状态

例

一个操作数序列，1,2,…,n（图示为 1 到 3 的情况），栈 A 的深度大于 n。

现在可以进行两种操作，

     一、将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）

     二、将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）

你的程序将对给定的 n，计算并输出由操作数序列 1,2,…,n 经过操作可能得到的输出序列的总数。

#include<bits/stdc++.h>
using namespace std;
//栈队列排序，每次两种操作，应该可以用递归，
//但像这种每次在上一次的基础上进行数次操作的题目，也可以用一个更为优越简单的方法——状态转移方程
//它的上一种状态和下一种状态有关系，而这种做法相较于其他枚举的方法，利用到了这一点
//状态转移：栈里有i个，已排的有j个，相当于：
//栈里有i-1个，已排有j个 和 栈里有i+1个，已排有j-1个的下一个情况
//即：ans[i][j]=ans[i-1][j]+ans[i+1][j-1]
//举例：假设有10个数。ans[1][9]=ans[2][9]+ans[0][10]
//ans[1][5]=ans[0][6]+ans[2][5] ans[3][0]=ans[2][1]+ans[4][0]
//那么只需把以上列举的这两种情况发生的总数加起来，便是栈里有i个，待排有j个的情况数  
main()
{
	long long ans[20][20]={0}; int n;  //自己第一次写都没搞清ans[i][j]中i和j的含义 
	cin>>n;                  //ans表示栈里的个数/已排号的个数 和总排入的没有关系，和待排的没有关系 
	for(int i=1;i<=n;i++)
	ans[i][0]=1;
    for(int j=1;j<=n;j++)  //确定边界有难度 
	for(int i=0;i<=n-j;i++) 
	{
		if(i==0)
		ans[i][j]=ans[i+1][j-1];
		else
		ans[i][j]=ans[i+1][j-1]+ans[i-1][j];
		cout<<i<<" "<<j<<" "<<ans[i][j]<<endl;
	}
	cout<<ans[0][n];
}

 

     3.作用，状态转移方程的特点和运行逻辑？

状态转移方程里最重要的两个核心就在它的名字上——“状态”和“转移”。

什么是状态?

状态，是一种稳定的、存储的、不会随外界轻易变化的量，它可以是某一段长式运算中间的某个状态，也可以是一幕难题落下帷幕后最后的那个答案，它记录着过程中的某一形态。

什么又是转移呢？从一状态变换到另一种状态便称为“转移”。转移是状态间不停回环流转直至最后帷幕落下的途径和通路，也是一个状态转移时最重要的依据和算法。

状态转移的关键是“从已知到更多的已知”这个过程的有限次重复，当从题目抽象出一个递推式时，最重要的便是设计一个推导顺序，让每后一次的递推需要的所有条件通过在它之前的递推确定下来。

 

如此，我们便理清了此方程的两个特点，它能够存储运算和实际过程中的某些状态，并将这些状态不停的转移进展，最后得到一个事物最终的状态——

也就是答案。

 

    4.运用，状态转移方程的优势

状态转移方程存储了状态，那么就意味着——

对于相同的状态，它只用去运算一次；它不用反复的去求解相同的状态

状态转移方程转移了状态，那么就意味着——

对于数据的处理，它找到并利用了不同状态间的关系；它发掘了内在的逻辑

 

对于大量的枚举，如若能找到其中可存储可转移的状态，运行时间便能大大减短；

对于每次繁琐的操作，这便已经确认了它的转移方式，只要找到能够表示题意的状态数组，便能大大缩短程序的复杂性

 

对于大多数正常枚举超时的题目来说，你使用的正常枚举并没有去囊括、去使用题目中所隐含的状态关系，即每一个状态不是相互独立的，但你仍然去重复的运算一个又一个有关联的状态，那么你的解法自然无法通过题目（你条件都没用完）。

 

    5.状态转移的使用

大多数题目中，你去找到一个状态关系并不算难事，难的是判断该种状态关系是否可行、该如何实施、该如何实现

一、状态转移方程中，需要初始化的状态

方程的作用是通过已知的状态进行延伸而后得到答案，答案即使状态双手的延伸；那么第一步，就是需要找出所有非延伸的、不辨自明的、所有延伸状态基础的初始状态

即，我们需要区分初始状态这个需要我们自己定义和赋值的，与其他由初始状态运算而来的延伸状态。

这是方程启动的关键

二、状态转移方程中，如何转移状态

你所延伸的状态必须是已求的

从一个或多个已知的状态转移到下一个未知的状态

这也变相的有个推论——

你所求的答案一定是最后一个状态。

 

     6.题目

简易. 题目中具有明确的转移方法和存储状态，具有明显的指向性

P1002 [NOIP2002 普及组] 过河卒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

中等. 题目中的转移方法和状态是抽象隐含的，没有什么指向性

P1077 [NOIP2012 普及组] 摆花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)