动态规划基础

何为dp：

动态规划(dynamic programming)，与分治相似的一种算法。

区别：
分治问题性质： 最优子结构

dp问题性质： 最优子结构+重叠子问题

dp主要用于解决最优化问题。当一个问题存在多个可行方案时，每个方案都对应着一个数值指标；我们的目标则是从这些方案中挑选出具有最优数值的那个或几个方案。

步骤：

1. 分析其最优子结构
2. 建立递归关系式
3. 求得其值 通常采用自顶向下的方法
4. 若需完成整个最优解方案

例题1： 矩阵连乘

    给定n个可以连乘的矩阵序列来计算乘积。由于矩阵乘法满足结合性，存在不同的计算次序。求解所需标量乘法最少的方案，用圆括号表示。  

样例输入：
5
3 4 2 1 6 5
样例输出：
65
((1,(2,3)),(4,5))

分析：
暴力？
方案数：
P(1) = 1;
P(n) = sum{P(k)*P(n-k)}
等于卡特兰数第n-1项 指数级增长

dp思路：
问题的两个性质：
最优子结构、重叠子问题。

1. 描述最优子结构
   长度为n的序列中存在n−1个划分点，在特定的一个划分下可以获得整体问题的最优解。

2.构造最优解
f[i,j] = 0 , i == j;
f[i, j] = min{f[i,