动态规划

一个问题是用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的。
递推：每个阶段只有一个状态。
贪心：每个阶段的最优状态都是由上一个阶段的最优状态得到。
搜索：每个阶段的最优状态是由之前所有阶段的状态的组合得到的。
动态规划；每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的。

1,动态规划特点：

1，最优子结构：每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到。
2，无后效性：而不管之前这个状态是如何得到。

1.1 分治与动态规划

共同点：二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小的子问题，然后将子问题的解合并,形成原问题的解。

不同点：分治法的子问题相互独立，通过用递归来做。动态规划的子问题有联系，有重叠部分，需要记忆，用迭代来做。

2,动态规划求解：

1，原问题拆成子问题（用状态表示）。
2，确定现在状态和之前状态之间的转移关系（递推关系）。从上往下分析，达到当前状态的前一步是什么（多种可能），从而确定状态转移方程。
3，最后以递推方式求解。

1,2是自上而下思考，3是自下而上求解。
有时原问题就能看做一个状态。例如01背包；有的不能，要先拆分，才能给出状态，如最长上升子序列。

例1：求a[n]的最长上升子序列

1，原问题拆分成子问题：以a[i]结尾的最长上升子序列，表示成状态f[i]。原问题=max(f[0],f[1],...,f[n-1])。
2，当前状态是以a[i]结尾，达到此状态的前一步是，它的前一位可能是a[0],a[1]...a[i-1]。故当前状态和之前状态的关系：f[i]=max(f[j])+1 ， j < i && a[j] < a[i].
3，递推求解。f[0]=1,f[1]=.......

例2：01背包

1，原问题状态为定义为f[i][v]。
2，达到f[i][v]状态的前一步可能是取物品i和不取物品i。所以f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
3，递推求解。

3,判断是否是动态规划

一般求最大值最小值、求可不可行、求方案总数的很可能是动态规划。如果一个问题让你求出所有的方案和结果，则肯定不是动态规划。
如果是动态规划，对其分类：

• 矩阵型
• 序列型
• 双序列型
• 划分型
• 区间型
• 背包型
• 状态压缩型
• 树型

在技术面试中经常出现的是：矩阵型，序列型和双序列型。
划分型，区间型和背包型偶尔出现。
状态压缩和树型基本不会出现（一般在算法竞赛中才会出现）。

每种类型都有着自己的题目特点和状态的表示方法。以矩阵型动态规划为例，一般题目会给你一个矩阵，告诉你有一个小人在上面走动，每次只能向右和向下走，然后问你比如有多少种方案从左上走到右下。这种类型状态表示的特点一般是使用坐标作为状态，如f[i][j]表示走到(i,j)这个位置的时候，一共有多少种方案。状态的转移则是考虑是从哪儿走到(i,j)这个坐标的。而序列型的动态规划，一般是告诉你一个序列；双序列的动态规划一般是告诉你两个字符串或者两个序列。将所做过的动态规划问题按照这些类别进行归类，分析状态的表示方法和状态转移方程的构造方法在每种类型中的近似之处，会让你更快的学会动态规划。

---

以上整理自知乎