Rod Cutting Problem | Dynamic Programming | Google | c++ solution

Problem Description:

There is a rod of length N lying on the 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, the 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 the same cost, return the lexicographically smallest.

Notes:

• Sequence a1, a2,…, an is lexicographically smaller than b1, b2,…, bm, if and only if at the first i where ai and bi differ, ai < bi, or if no such i found, then n < m.
• N can be up to 109.

For example,

N = 6
A = [1, 2, 5]

If we make cuts in order [1, 2, 5], let us see what total cost would be.
For first cut, the length of rod is 6.
For second cut, the length of sub-rod in which we are making cut is 5(since we already have made a cut at 1).
For third cut, the length of sub-rod in which we are making cut is 4(since we already have made a cut at 2).
So, total cost is 6 + 5 + 4.

Cut order          | Sum of cost
(lexicographically | of each cut
 sorted)           |
___________________|_______________
[1, 2, 5]          | 6 + 5 + 4 = 15
[1, 5, 2]          | 6 + 5 + 4 = 15
[2, 1, 5]          | 6 + 2 + 4 = 12
[2, 5, 1]          | 6 + 4 + 2 = 12
[5, 1, 2]          | 6 + 5 + 4 = 15
[5, 2, 1]          | 6 + 5 + 2 = 13


So, we return [2, 1, 5].

 

Approach:

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

We define DP(i, j) as the 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(N3).
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.

Problem Solution in C++ Programming Language:

code:

vector<int> ans;

void find_ans(vector<vector<int>> pa, int l, int r)

{

    if(pa[l][r] == -1) return;

    else

    {

        ans.push_back(pa[l][r]);

        find_ans(pa, l, pa[l][r]);

        find_ans(pa, pa[l][r], r);

    }

}

vector<int> Solution::rodCut(int A, vector<int> &B) {

    int m = B.size();

    ans.clear();

    vector<int> B1(m+2);

    B1[0] = 0; B1[m+1] = A;

    for(int i = 0; i<m; i++) B1[i+1] = B[i];

    vector<vector<int>> dp(m+2, vector<int>(m+2, INT_MAX)), pa(m+2, vector<int>(m+2, -1));

    for(int i = m+1; i>=0; i--)

    {

        for(int j = 0; j<m+2; j++)

        {

            if(i == j)

            {

                dp[i][j] = 0;

                continue;

            }

            if(i>j) continue;

            int cost = B1[j] - B1[i];

            for(int k = i+1; k<j; k++)

            {

                if(dp[i][j] > dp[i][k] + dp[k][j] + cost)

                {

                    dp[i][j] = dp[i][k] + dp[k][j] + cost;

                    pa[i][j] = k;

                }

            }

        }

    }

    

    find_ans(pa, 0, m+1);

    vector<int> final_ans(m);

    for(int i = 0; i<m; i++)

    {

        final_ans[i] = B[ans[i]-1];

    }

    return final_ans;

}

Please share your reviews.

thanks for reading.👍😊

If you like the solution please share with your friends.

and for more dynamic programming question for interview preparation.