03.动态规划
动态规划
动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems. The key for dp is to find the variables to represent the states and deduce the transition function.
适合采用动态规划方法的最优化问题的俩个要素：最优子结构性质，和子问题重叠性质。
- 最优子结构：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质(即满足最优化原理)。意思就是，总问题包含很多个子问题，而这些子问题的解也是最优的。
- 重叠子问题：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
总结而言，一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的：
- 每个阶段只有一个状态 -> 递推；
- 每个阶段的最优状态都是由上一个阶段的最优状态得到的 -> 贪心；
- 每个阶段的最优状态是由之前所有阶段的状态的组合得到的 -> 搜索；
- 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的 -> 动态规划。动态规划算法一般是 n 步叠代计算局部最优解，每一步叠代需要计算 m 个子项，那么时间复杂度就是
O(m*n)。如果只保存一步叠代的结果，空间复杂度就是O(m)；如果需要保存 k 步叠代结果，空间复杂度就是O(m*k)。
动态规划求解
求解动态规划的关键，是对问题状态的定义和状态转移方程的定义。动态规划中递推式的求解方法不是动态规划的本质。动态规划算法分以下 4 个必须步骤：
- 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的(即无后向性)，否则问题就无法用动态规划求解。
- 描述最优解的结构，即状态的定义：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。无后向性即每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到但是不用管之前的状态是如何得到的。
- 递归定义最优解的值，即状态转移方程的定义。
- 按自底向上的方式计算最优解的值。
- 由计算出的结果构造一个最优解。// 此步如果只要求计算最优解的值时，可省略。
这里我们以 LIS 问题做一个实例讲解，给定一个数列，长度为 N，求这个数列的最长上升(递增)子数列(LIS )的长度。以 1 7 2 8 3 4 为例，这个数列的最长递增子数列是 1 2 3 4，长度为 4；次长的长度为 3，包括 1 7 8; 1 2 3 等。首先我们对这个问题进行阶段划分，可以看出求某个数列的最长递增子数列这个问题肯定可以划分为多个阶段进行处理，即具备了最优子结构与重叠子问题。下面我们定义解的结构，即状态，给定一个数列，长度为 N，设 $F_k$ 为：以数列中第 k 项结尾的最长递增子序列的长度。求解 $F_1 \dots F_N$ 中的最大值。那么状态转移方程，即 DP 方程也就是：
$$ \left {\begin{aligned}F_1 = 1 \F_k = max(F_i + 1 | A_k > A_i, i \in (1 \dots k-1))(k>1) \\end{aligned}\right. $$