Dynamic Programming - Rod Cutting Problem

This is one of the famous interview questions and most of you faced this question in the interview.

Question: Given a rod of length n and list of prices of rod of length i where 1 <= i <= n, find the optimal way to cut rod into smaller rods in order to maximize profit.

Program:

#include<iostream>
#include<algorithm>

using namespace std;

#define ROD_CUTS 4
#define LEN      5

int rodSize[ROD_CUTS] = {1, 2, 3, 4};
int rodSizeCost[ROD_CUTS] = {2, 5, 7, 8};
int costMatrix[ROD_CUTS][LEN+1] = {0};

int findCost(int i, int j)
{
   if(i < 1)
      return costMatrix[i][j-rodSize[i]]+rodSizeCost[i];
   else
   {
      if(j < rodSize[i])
         return costMatrix[i-1][j];
      else
         return std::max(costMatrix[i][j-rodSize[i]]+rodSizeCost[i], costMatrix[i-1][j]);
   }
}

int main()
{
   for(int i=0; i<ROD_CUTS; ++i)
   {
      for(int j=1; j<=LEN; ++j)
      {
         costMatrix[i][j] = findCost(i, j);
      }
   }
   cout << "Maximum Profit = " << costMatrix[ROD_CUTS-1][LEN] << endl;
   return 0;
}

Output:

Maximum Profit = 12