Skip to content

1547. Minimum Cost to Cut a Stick 👍

Approach 1: Top-down

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int minCost(int n, vector<int>& cuts) {
    cuts.push_back(0);
    cuts.push_back(n);
    ranges::sort(cuts);
    vector<vector<int>> mem(cuts.size(), vector<int>(cuts.size(), INT_MAX));
    return minCost(cuts, 0, cuts.size() - 1, mem);
  }

 private:
  // Returns minCost(cuts[i..j]).
  int minCost(const vector<int>& cuts, int i, int j, vector<vector<int>>& mem) {
    if (j - i <= 1)
      return 0;
    if (mem[i][j] != INT_MAX)
      return mem[i][j];

    for (int k = i + 1; k < j; ++k)
      mem[i][j] = min(mem[i][j], cuts[j] - cuts[i] + minCost(cuts, i, k, mem) +
                                     minCost(cuts, k, j, mem));

    return mem[i][j];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int minCost(int n, int[] cuts) {
    int[] extendedCuts = new int[cuts.length + 2];
    int[][] mem = new int[extendedCuts.length][extendedCuts.length];
    System.arraycopy(cuts, 0, extendedCuts, 1, cuts.length);
    extendedCuts[0] = 0;
    extendedCuts[extendedCuts.length - 1] = n;
    Arrays.sort(extendedCuts);
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    return minCost(extendedCuts, 0, extendedCuts.length - 1, mem);
  }

  // Returns minCost(cuts[i..j]).
  private int minCost(int[] cuts, int i, int j, int[][] mem) {
    if (j - i <= 1)
      return 0;
    if (mem[i][j] != Integer.MAX_VALUE)
      return mem[i][j];

    for (int k = i + 1; k < j; ++k)
      mem[i][j] = Math.min(mem[i][j],
                           cuts[j] - cuts[i] + minCost(cuts, i, k, mem) + minCost(cuts, k, j, mem));

    return mem[i][j];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def minCost(self, n: int, cuts: list[int]) -> int:
    A = sorted([0] + cuts + [n])

    @functools.lru_cache(None)
    def dp(i, j):
      if j - i <= 1:
        return 0

      return min(A[j] - A[i] + dp(i, k) + dp(k, j) for k in range(i + 1, j))

    return dp(0, len(A) - 1)

Approach 2: Bottom-up

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int minCost(int n, vector<int>& cuts) {
    cuts.push_back(0);
    cuts.push_back(n);
    ranges::sort(cuts);

    // dp[i][j] := minCost(cuts[i..j])
    vector<vector<int>> dp(cuts.size(), vector<int>(cuts.size()));

    for (int d = 2; d < cuts.size(); ++d)
      for (int i = 0; i + d < cuts.size(); ++i) {
        const int j = i + d;
        dp[i][j] = INT_MAX;
        for (int k = i + 1; k < j; ++k)
          dp[i][j] = min(dp[i][j], cuts[j] - cuts[i] + dp[i][k] + dp[k][j]);
      }

    return dp[0][cuts.size() - 1];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int minCost(int n, int[] cuts) {
    int[] A = new int[cuts.length + 2];
    System.arraycopy(cuts, 0, A, 1, cuts.length);
    A[0] = 0;
    A[A.length - 1] = n;

    Arrays.sort(A);

    // dp[i][j] := minCost(cuts[i..j])
    int[][] dp = new int[A.length][A.length];

    for (int d = 2; d < A.length; ++d)
      for (int i = 0; i + d < A.length; ++i) {
        final int j = i + d;
        dp[i][j] = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; ++k)
          dp[i][j] = Math.min(dp[i][j], A[j] - A[i] + dp[i][k] + dp[k][j]);
      }

    return dp[0][A.length - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def minCost(self, n: int, cuts: list[int]) -> int:
    A = sorted([0] + cuts + [n])

    dp = [[0] * len(A) for _ in range(len(A))]

    for d in range(2, len(A)):
      for i in range(len(A) - d):
        j = i + d
        dp[i][j] = math.inf
        for k in range(i + 1, j):
          dp[i][j] = min(dp[i][j], A[j] - A[i] + dp[i][k] + dp[k][j])

    return dp[0][len(A) - 1]