3. Dynamic Programming

Think

1. Lot of start,end
   Every stey have associative and we need solve small question to big question.Finaly, subquestion is atomic question.Every subquestion of value hava dependent relative,what to use result to provide back subquestion.

Design

1. Make sure subquestion border
2. Optimize recusive equations
3. Attention cut position

Step

1. 引入参数来界定子问题的边界
2. 判断该优化问题是否满足优化原则
3. 注意子问题的重叠程度
4. 分析子问题的之间依赖关系
5. 采用自底向上的实现技术
6. 利用备忘录和标记函数通过追溯得到最优解
7. 动态规划算法的时间复杂度与子问题个数计算的工作量
8. 由于备忘录来存储中间结果，往往需要使用较多的储存空间至于规模较大的问题，就成为性能的瓶颈

Implement

1. Use Recursion

    for(int r = 2; r <= n; r++) { // chain of length [0 - n]  子问题划分 
        for(int i = 1; i <= (n-r+1); i++) { //  n-1+1 遍历其中的元素 
            int j = i + r -1; // j = 1 + 2 - 1 = 2 // 从子问题起始点 
            m[i][j] = m[i+1][j] + data[i-1]*data[i]*data[j];  // 计算当前数据 data[0]data[1]data[2] +m[2,2] = 优化值 m[1,2]
            s[i][j] = i; //s[i][j] = i;  标记元素 = 坐标 记录分割位置 s[1,2] = 1
            for(int k = i + 1; k <= j - 1; k++) { // 寻找其他划分 k = 2 < 2 - 1 
                int t = m[i][k] + m[k+1][j] + data[i-1]*data[k]*data[j]; // 前面的 + 后面的 + 相乘数据
                if (t < m[i][j]) {
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
        }
    }

2. Use Iterative

int recur(int* data,int i, int j) {
    if (i == j) { // 递归到最小单元 如 data[1][1] = 0; data[1][1]=1
        m[i][j] = 0;
        s[i][j] = i;
        return m[i][j]; 
    }
    m[i][j] = 1 << 30; // 该i到j 赋予最大值
    s[i][j] = i; // 分割点在i
    for (int k = i; k <= j-1; k++) { // 从i到j-1开始递归处理求最小值，在加上整体数据
        int q = recur(data, i, k) + recur(data, k+1, j) + data[i-1]*data[k]*data[j]; //data[0]*data[k]*data[j]
        if (q < m[i][j]) {
            m[i][j] = q;
            s[i][j] = k;
        }
    }
    return m[i][j];
}