自下而上的动态规划算法

　　动态规划是我们耳熟能详的基本算法。动态规划是全局状态下的最优解，不同于贪心算法。贪心算法是每次找出当前状态下的最优解，但是全局并不一定是最优解。接下来我们通过《算法导论》书上的一个经典例题来完成对动态规划的学习——钢条切割问题。

　　问题描述：　　Serling公司购买长钢条，将其切割为短钢条出售。切割工艺本身没有成本支出。公司管理层希望知道最佳的切割方案。

　　价格表用例：　　

长度 i	1	2	3	4	5	6	7	8	9	10
价格 p	1	5	8	9	10	17	17	20	24	30

　　分析：此问题的求解就是把一定长度的钢条分为两段，然后再分别求解每段所带来的价值。对此，我们可以简化一下。首先规定住一定的长度的钢条，不断求解剩余部分，也就是说把求解两部分转化为不断求解一部分，这样想来可以利用递归来实现。递归版本的伪代码为：

cutRod(p, n){
    if(n == 0)
        return 0;
    q = -oo;
    for(I = 0; I <= n; ++i){
        q = max(q, p[i] + cutRod(p, n-i));
    }
     return q;       
}

　　　　递归的时间复杂度不能够忍受，小规模还好，大规模运行时间太长。但是递归未尝不是一个方法。在这里我们引出我们今天的主角——动态规划。动态规划有两个版本：自底向上和自上而　　　　　　　　　　     下。自底向上的动态规划容易理解，我们来学习一下。核心思想是采取一个记忆数组存放每段长度的最优解，并以此作为求解大数值的最优解。也就是说，先求出长度为1的最优解，再求出　　     2......等求解大数值时，分解出的各类小数值已经知晓可以直接拿来调用。这其中，记忆数组尤为重要，也比较不容易理解。C++版本的代码如下：

#include <iostream>
using namespace std;

int temp[100];
int calculate(int *price, int n){
    temp[0] = 0;
    int a;
    for(int i = 1; i <= n; ++i) {
        a = -128;
        for(int j = 1; j <= i; ++j){
            if(a < price[j] + temp[i - j]){
                a = price[j] + temp[i - j];
            }
        }
        temp[i] = a;
    }
    return temp[n];
}

int main() {
    int p[11] = {0,1,5,8,9,10,17,17,20,24,30};
    int n = 10;
    cout<<calculate(p, n)<<endl;

    return 0;
}

PS：限于知识有限，言语中定有疏忽不能发现，希望读者能够不吝赐教，万分感激！