Minimum Cost to Cut a Stick of length N

JavaView on GFG

Time: O(n^3)

Space: O(n^2)

Intuition

Minimum cost to cut a stick at given positions. Interval DP.

Algorithm

1Add 0 and n as boundaries. dp[i][j] = min cost to cut stick between positions[i] and positions[j].
2dp[i][j] = min over all k in (i,j): dp[i][k] + dp[k][j] + positions[j]-positions[i].

Common Pitfalls

•Same as LC 1547. Interval DP on sorted cut positions. O(m^3) where m = number of cuts.

Minimum Cost to Cut a Stick of length N.java

Java

// Approach: Interval DP. dp[i][j] = min cost to cut stick between cuts[i] and cuts[j].
// Time: O(n^3) Space: O(n^2)
class Solution {
    public int minCutCost(int n, int[] cuts) {
        int m = cuts.length;
        int[] arr = new int[m + 2];
        for (int i = 0; i < m; i++)
            arr[i + 1] = cuts[i];
        arr[0] = 0;
        arr[m + 1] = n;
        java.util.Arrays.sort(arr);

        int[][] dp = new int[m + 2][m + 2];

        for (int len = 2; len < m + 2; len++) {
            for (int i = 0; i + len < m + 2; i++) {
                int j = i + len;
                int best = Integer.MAX_VALUE;

                for (int k = i + 1; k < j; k++)
                    best = Math.min(best, dp[i][k] + dp[k][j] + arr[j] - arr[i]);

                dp[i][j] = best == Integer.MAX_VALUE ? 0 : best;
            }
        }

        return dp[0][m + 1];
    }
}

Was this solution helpful?