本文针对两篇优秀动态规划文章中存在的不易理解的部分：状态、状态转移的定义和状态转移方程的编程实现部分进行个人解读。欢迎指出本文存在的错误和表述不清之处。

DP概述

DP(Dynamic Programming)是算法设计中解决最优化问题(eg: 最长公共子序列)的重要思想。
（待补充）
因此我们可以得出结论:

动态规划的本质，是对问题状态的定义和状态转移方程的定义。
——什么是动态规划？动态规划的意义是什么？(徐凯强 Andy的回答)

状态

这里给出我自己的一个定义后面会解释：

从“原始的最优化问题”剥离出的每个“最优化子问题”都是当前DP问题的一个状态，每个状态分布在“每次的决策前后”。

我们现在来看两个简单的动态规划问题：

问题1：
给定一个数列A，长度为N，
求这个数列的最长上升（递增）子数列（LIS）的长度.
以
1 7 2 8 3 4
为例。
这个数列的最长递增子数列是 1 2 3 4，长度为4；
次长的长度为3， 包括 1 7 8; 1 2 3 等.

剥离出的子问题，以及等价最终问题：
给定一个数列A，长度为N
设F(x)：以数列A中第x项结尾的最长递增子序列的长度, 其中0 <= x <= N 。(子问题or状态)
求F(1)..F(N)中的最大值 (等价最终问题)

问题2:
如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？

剥离出的子问题，以及等价最终问题：
如果我们有面值为1元、3元和5元的硬币若干枚
设D(i)：凑够i元使用最少硬币个数，其中 0 <= i <= 11。(子问题or状态)
求D(11)的值。 (等价最终问题)

这两个问题便是“原始的最优化问题”。现在，根据“状态和状态转移方程的定义是动态规划的本质”的结论，我们需要做的就是从“原始的最优化问题”中找出状态，然后再得到状态转移方程，之后根据状态转移方程实现代码(其间还会使用到记忆和重叠子问题特性)，最终得到解。

• 剥离子问题，获得状态(最需要技巧和训练的部分)
  之前说过，DP中的状态就是子问题。显然，我们要获得状态就必须剥离(拆分)“原始的最优化问题”。这里通过分析问题1和问题2剥离好的子问题探索一下DP中剥离（拆分）问题的“奇淫巧技”。

  首先拿到一个DP问题，我们最先要思考的是: 该问题的“变数”在哪里？这里的“变数”很重要，问题的“变数”往往是整个问题定义中的一个参数，当我们改变这个参数时，将会使问题的规模缩小。 例如，问题1的变数是数列A的大小，当我们改变数列A的大小时，问题1的规模变缩小了。因此，我们才这样剥离问题1:"F(x)是以A[x]为结尾的LIS的长度，且 0<= x <= N"。显然，此时若x 等于 N-1，我们把问题缩小了单位1长度；此时若x等于0，我们则把问题缩小成了0，显然此时还触碰到了当前问题的边界：“数列长度必须大于等于0”。问题2中也可套用同样的思路: 我们可以把最终需要凑够的价格i元作为变数，当我们改变i元的大小时，问题2的规模同样被缩小了。因此我们才这样重新定义问题2:"D(i)是凑够i元需要的最少硬币个数"。此时若i等于0，我们同样到达了当前问题的边界:"凑钱不可能凑出负数"。

  因此，DP剥离子问题需要多联系"当前问题中可能的变数"，同时多加练习。

• DP中每个子问题都是状态，分布在每次决策前后
  把DP中的子问题问题叫做状态有两方面原因。

• 为了区分问题和子问题而产生的叫法。

之所以把Fx叫做“状态”而不是“问题” ，一是因为避免跟原问题中“问题”混淆，二是因为这个新问题是数学化定义的。
——什么是动态规划？动态规划的意义是什么？(徐凯强 Andy的回答)

• 状态二词更能准确表示出DP子问题是什么

从前面对剥离子问题的分析大抵可以感受到这么一个过程: 整个DP问题从问题的定义边界开始(比如: 数列之长度为0，凑钱之总额为0)，到问题收敛处为止(比如: 数列之长度为N，凑钱之总额为0)，算法的每次决策都在推动前一个子问题发展到后一个子问题，往往这种推动都有多种可能性

比如:A={1 7 2 8 3 4}，从当前F(3)={1，2}到F(6)时，我们可以很机智地选择从F(5) = {1,2,3}走最优解到F(6)={1,2,3,4}。但我们也可以任性地选择F(5)={1,2}到F(6)={1,2,4}，或者F(5)={1,2,3},F(6)={1,2,3}..以及其他多种可能性)。此时我们可以在子问题之间以不同的状态(如F(5)={1,2,3} 或者F(5)={1,2})进行转移(比如从F(5)={1,2,3}到F(6)={1,2,3,4})，因此把子问题叫做“状态”，把子问题间的转移叫做“状态转移”是很形象的说辞。

状态转移方程

对状态的解释已经触及到了状态转移的概念:“子问题间通过决策进行推演的过程叫做状态转移”。所以，状态转移方程就应该是“子问题间通过决策定义的等式关系叫做状态转移方程”，通常状态转移方程和当前问题的边界条件联立起来叫做状态转移方程式。

——什么是动态规划？动态规划的意义是什么？(徐凯强 Andy的回答)

——动态规划：从新手到专家

显然，max(), min()就代表着一种最优决策。我们如果把max或者min去掉，那么上面的方程式依然可以叫做状态转移方程，只是得到的结果不一定是最优解了。

编程实现

初学者在解DP问题时，如何编程实现状态转移方程？如何在DP求解过程中利用重叠子问题进行记忆求解？
让我们看一下问题2的伪代码:

从伪代码我们可以分析出一个较为通用的DP代码实现过程：（S代表总额，N-1代表可能的硬币面值）

• 首先我们需要存储每个子问题的最优解，比如伪代码中使用Min[i]数组存储每个子问题的最优解。
• 然后我们需要对DP问题的边界的解进行初始化，比如伪代码中Min[0] = 0代表着边界条件"凑够0元需要的最少硬币数"的解。
• 定义好边界解后，我们就可以从边界解开始，使用递归的方法自底向上的求解DP的每个子问题，并把子问题的最优解记录下来。比如，伪代码中从i = 1开始求解直到i = s,每次得到的子问题最优解都被存储在Min[i]中。
• 最后，根据特定的题目，或直接输出某个子问题的最优解，或对所有子问题的最优解进行处理以后再进行输出。比如：硬币问题我们可以直接输出Min[11]。而LIS问题我们需要比较F(x),x = 0,1,2...N， 然后输出F(x)的最大值。

引用

什么是动态规划？动态规划的意义是什么？
http://www.hawstein.com/posts/dp-novice-to-advanced.html
动态规划：从新手到专家
https://www.zhihu.com/question/23995189