动态规划问题——刚条切割

#include <iostream>
#include <limits.h>
using namespace std;

int cut_rod(int *arr,int n)//自顶向下递归算法
{
    if(n==0)
        return 0;
    int q=INT_MIN;
    for(int i=1;i<=n;i++)
    {
        int t=cut_rod(arr,n-i);
        q=q>arr[i]+t?q:arr[i]+t;
    }
    return q;
}

int memorized_cut_rod_aux(int *arr,int n, int *r)//top down with memorization
{
    int q;
    if(r[n]>=0)
        return r[n];
    if(n==0)
        q=0;
    else
    {
        q=INT_MIN;
        for(int i=1;i<=n;i++)
        {
            int t=memorized_cut_rod_aux(arr,n-i,r);
            q=q>arr[i]+t?q:arr[i]+t;
        }
    }
    r[n]=q;
    return q;
}

int memorized_cut_rod(int *arr,int n)
{
    int r[n+1];
    for(int i=0;i<n+1;i++)
    {
        r[i]=INT_MIN;
    }
    return memorized_cut_rod_aux(arr,n,&r[0]);
}

int bottom_up_cut_rod(int *arr, int n)//bottom_up_cut_rod
{
    int r[n+1];
    r[0]=0;
    for(int j=1;j<=n;j++)
    {
        int q=INT_MIN;
        for(int i=1;i<=j;i++)
        {
            q=q>arr[i]+r[j-i]?q:arr[i]+r[j-i];

        }
        r[j]=q;
    }
    return r[n];
}

int extended_bottom_up_cut_rod(int *solu,int *arr, int n)//bottom_up_cut_rod
{
    int r[n+1];
    r[0]=0;
    for(int j=1;j<=n;j++)
    {
        int q=INT_MIN;
        for(int i=1;i<=j;i++)
        {
            //q=q>arr[i]+r[j-i]?q:arr[i]+r[j-i];
            if(q<arr[i]+r[j-i])
            {
                solu[j]=i;
                q=r[j]=arr[i]+r[j-i];
            }

        }
    }
    return r[n];
}
  
int main()
{
    int arr[11]={0,1,5,8,9,10,17,17,20,24,30};
    //cout<<cut_rod(&arr[0],40);
    //cout<<memorized_cut_rod(&arr[0],40);
    //cout<<bottom_up_cut_rod(&arr[0],10)<<endl;
    int n=8;
    /*for(int i=1;i<=10;i++)
        cout<<bottom_up_cut_rod(&arr[0],i)<<endl;
    */

    int sol[n+1];
    cout<<extended_bottom_up_cut_rod(&sol[0],&arr[0],n)<<endl;
    while(n>0)
    {
        cout<<sol[n]<<",";
        n=n-sol[n];
    }
    return 0;
}