本博文资料来源于算法导论第三版

动态规划有两种等价实现方法：带备忘的自顶向下发（topDownWithMemoization）,自底向上方法，付出额外的内存空间来节省计算时间，是典型的时空权衡，递归时会保存每个子问题的解

长度n与对应价格p关系

1~10的对应最优收益

朴素递归之自顶向下方法伪代码

c++代码

#include <iostream>

using namespace std;

upDownCutRod(int p[],int n)
{
    if(n==0)
        return 0;
    int q=-1;
    for(int i=0;i<n;++i)
        q=max(q,p[i]+upDownCutRod(p,n-i-1));
    return q;
}

int main()
{
    int p[10]={1,5,8,9,10,17,17,20,24,30};
    int q=upDownCutRod(p,10);
    cout<<"最优收益值为："<<q;
    return 0;
}

运行结果

动态规划自顶向下伪代码

c++代码实现

#include <iostream>

using namespace std;

int memorizedCutRodAux(int p[],int n,int r[])
{
    int q;//最大收益值
    if(r[n]>=0)
        return r[n];//检查所需值是否已知
    if(n==0)
        q=0;//n=0时不会有收益
    else
    {
        q=-1;
        for(int i=0;i<n;++i)
            q=max(q,p[i]+memorizedCutRodAux(p,n-i-1,r));
    }
    r[n]=q;
    return q;
}

memorizedCutRod(int p[],int n)
{
    int r[n+1];
    for(int i=0;i<=n;++i)
        r[i]=-1;
    return memorizedCutRodAux(p,n,r);
}

int main()
{
    int p[10]={1,5,8,9,10,17,17,20,24,30};
    int q=memorizedCutRod(p,10);
    cout<<"带备忘的自顶向下方法的最优收益值为："<<q;
    return 0;
}

运行结果

自底向上方法伪代码

c++代码实现

#include <iostream>

using namespace std;

int bottomUpCutRod(int p[],int n)
{
    int r[n+1];//记录不同规模子问题的解，这里是1~10
    int q;//记录收益
    r[0]=0;
    for(int j=1;j<=n;++j)
    {
        q=-1;//初始为负，常见的表示未知数的方法
        for(int i=1;i<=j;++i)
        {
            q=max(q,p[i-1]+r[j-i]);//不再使用递归
        }
        r[j]=q;
    }
    return r[n];
}

int main()
{
    int p[10]={1,5,8,9,10,17,17,20,24,30};
    int q=bottomUpCutRod(p,10);
    cout<<"自底向上方法的最优收益值为："<<q;
    return 0;
}

运行结果