Problem Statement

There is a rod of length N lying on x-axis with its left end at x = 0 and right end at x = N. Now, there are M weak points on this rod denoted by positive integer values(all less than N) A1, A2, …, AM. You have to cut rod at all these weak points. You can perform these cuts in any order. After a cut, rod gets divided into two smaller sub-rods. Cost of making a cut is the length of the sub-rod in which you are making a cut.

Your aim is to minimise this cost. Return an array denoting the sequence in which you will make cuts. If two different sequences of cuts give same cost, return the lexicographically smallest.

Notes:

Problem Link

Rod Cutting - InterviewBit

Approach

We rewrite our problem as given N cut points(and you cannot make first and last cut), decide order of these cuts to minimise the cost. So, we insert 0 and N at beginning and end of vector B. Now, we have solve our new problem with respect to this new array(say A).

We define dp(i, j) as minimum cost for making cuts Ai, Ai+1, ..., Aj. Note that you are not making cuts Ai and Aj, but they decide the cost for us.

For solving dp(i, j), we iterate k from i+1 to j-1, assuming that the first cut we make in this interval is Ak. The total cost required(if we make first cut at Ak) is Aj - Ai + dp(i, k) + dp(k, j).

This is our solution. We can implement this DP recursively with memoisation. Total complexity will be O(N^3).

For actually building the solution, after calculating dp(i, j), we can store the index k which gave the minimum cost and then we can build the solution backwards.

Code

typedef long long int ll;
vector<vector<ll>> dp;
vector<int> res;
vector<vector<int>> parent;
vector<int> cuts;
ll recur(int l,int r)
{
   
    if(l+1>=r)
    return 0;
    
    if(dp[l][r]!=-1)
    return dp[l][r];
   
    dp[l][r] = LLONG_MAX;
    int best_idx;
    for(int i=l+1;i<r;i++)//performing cuts at cuts[i] 
    {
        ll ret = recur(l,i) + recur(i,r) + cuts[r] - cuts[l];
        
        if(ret<dp[l][r])
        {
            dp[l][r] = ret;
            best_idx = i;
        }
    }
   
    parent[l][r] = best_idx;
    
    return dp[l][r];
}

void formarray(int l,int r)
{
    if(l+1>=r)
    return;
    
    res.push_back(cuts[parent[l][r]]);
    
    formarray(l,parent[l][r]);
    formarray(parent[l][r],r);
}

vector<int> Solution::rodCut(int n, vector<int> &B) {
    
    
    B.push_back(n);
    B.insert(B.begin(),0);
    int m = B.size();
    
    dp.clear();
    dp.resize(m,vector<ll>(m,-1));
    
    res.clear();
    parent.clear();
    parent.resize(m,vector<int>(m));
    cuts.clear();
    cuts.resize(m);
    
    for(int i=0;i<m;i++)
    cuts[i] = B[i];
   
    ll mincost = recur(0,m-1);
    
    formarray(0,m-1);
    
    return res;
    
   
    
}