# 第 5 节状态与状态转移方程

# 定义状态：定义子问题

我们在拆分子问题的时候，会想到一个问题：如何描述子问题。而描述子问题这件事情就叫做 定义状态。

PS：我也不知道为什么定义子问题要叫成定义状态，初学的时候真的很难懂（哭泣）。

状态的定义一定要非常精准，例如：

这两件事情是完全不一样的，状态的不同定义会导致状态转移方程大相径庭。具体应该如何定义，要看具体问题，一旦定义好，在状态转移的时候就要保持这个定义。

状态转移方程描述了不同规模子问题之间的关系。

由于求汇总值有这样的特点：由小规模的问题的解可以得到大规模的问题的解。大家想想是不是这样：求最小值、最大值、计数（根据分类计数加法原理）。下面这张图展示了一个具体的例子，帮助大家理解。

这件事情，在动态规划里就叫做「状态转移」。

PS：所以状态转移方程就是个等式呀，为什么要叫方程呢？要求解未知数嘛？哪儿来的「转移」呢？转到哪里去，又移动了什么呢？为什么又要推导呢？初学的时候，真叫人头大啊，哈哈哈哈！

作者：liweiwei1419 链接：https://suanfa8.com/dynamic-programming/state-transition 来源：算法吧著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。