DP-rodcutting

rodcutting1Darray.cpp

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

int main()
{
    int size;
    cin >> size;
    int profit[size];
    for(int i = 0; i < size; i++) cin >> profit[i];
    int dp[size + 1];
    memset(dp, 0, sizeof dp);
    for(int i = 1; i <= size; i++){
        int mxvalue = 0;
        for(int j = 1; j <= i; j++){
            mxvalue = max(mxvalue, profit[j - 1] + dp[i - j]);
        }
        dp[i] = mxvalue;
    }
    cout << dp[size] << '\n';

    return 0;
}

rodcuttingRecursion.cpp

#include <iostream>
using namespace std;
int size;
int* pr;
int* sv;
int rodcutting(int n)
{
    if(n <= 0) return 0;
    int mx = -1;
    for(int i = 1; i <= n; i++){
        mx = max(mx, pr[i] + rodcutting(n - i));
    }
    return mx;
}

int main()
{
    cin >> size;
    pr = new int[size + 1];
    for(int i = 1; i <= size; i++) cin >> pr[i];
    sv = new int[size + 1];
    cout << rodcutting(size) << endl;


    return 0;
}