## Thursday, December 19, 2019

### 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

### Arrays in Solidity Programming Language.

Arrays Solidity supports both generic and byte arrays. It supports both fixed size and dynamic arrays. It also supports multidimensional ...