Rod cutting problem

Rod cutting problem is a classical DP problem and it is the first example in the very classical textbook “Introduction to ALGORITHMS”.

The problem

The description of the problem can be found HERE.

TOP-DOWN DP solution

#include <bits/stdc++.h>
using namespace std;
int memo[1000];
int dp(vector<int>& prices, int i)
{
    if (i==0)return memo[i] = 0;
    if (memo[i]!=-1) return memo[i];
    int ret = prices[i-1];
    for (int k = 1; k < i; ++k)
    {
        ret = max(ret, dp(prices, k) + dp (prices, i - k));
    }
    return memo[i] = ret;
}
int main()
{
    memset(memo, -1, sizeof memo);
    vector<int> prices = {1, 5, 8, 9, 10, 17, 17, 20}; 
    const int n = prices.size();
    printf("Maximum Obtainable Value is %d\n", dp(prices, n));
    return 0; 
}

A similar and harder Leetcode Problem

It can be found HERE.