Maximize The Cut Segments

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Cut rope of length n into maximum pieces of lengths x, y, or z. Unbounded knapsack DP.

Algorithm

1dp[i] = max(dp[i-x], dp[i-y], dp[i-z]) + 1. Base dp[0]=0. If dp[n] == -INF: return 0.

Common Pitfalls

•Initialize dp with -INF (not -1 to distinguish impossible). Max cuts is unbounded knapsack count variant.

Maximize The Cut Segments.java

Java

// Approach: DP. dp[i] = max cuts of length i using segments of size x, y, z. dp[i] = max over valid dp[i-x]+1 etc.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    // Function to find the maximum number of cuts.
    public int maximizeCuts(int n, int x, int y, int z) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);

        return Math.max(0, topDown(n, x, y, z, dp));
    }

    int topDown(int n, int x, int y, int z, int[] dp) {
        if (n == 0)
            return 0;

        if (n < 0)
            return Integer.MIN_VALUE;

        if (dp[n] != -1)
            return dp[n];

        int xpath = topDown(n - x, x, y, z, dp);
        int ypath = topDown(n - y, x, y, z, dp);
        int zpath = topDown(n - z, x, y, z, dp);

        return dp[n] = 1 + Math.max(xpath, Math.max(ypath, zpath));
    }
}

Was this solution helpful?