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
26
27
28
29
30
class Solution {
 public:
  int minCost(int n, vector<int>& cuts) {
    cuts.push_back(0);
    cuts.push_back(n);
    sort(begin(cuts), end(cuts));

    // dp[i][j] := minCost(cuts[i..j])
    dp.resize(cuts.size(), vector<int>(cuts.size()));
    return minCost(cuts, 0, cuts.size() - 1);
  }

 private:
  vector<vector<int>> dp;

  int minCost(const vector<int>& cuts, int i, int j) {
    if (j - i <= 1)
      return 0;
    if (dp[i][j])
      return dp[i][j];

    dp[i][j] = INT_MAX;

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

    return dp[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
27
28
29
30
31
class Solution {
  public int minCost(int n, int[] cuts) {
    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])
    dp = new int[A.length][A.length];
    return minCost(0, A.length - 1);
  }

  private int[][] dp;
  private int[] A;

  private int minCost(int i, int j) {
    if (j - i <= 1)
      return 0;
    if (dp[i][j] != 0)
      return dp[i][j];

    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] + minCost(i, k) + minCost(k, j));

    return dp[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])

    @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);
    sort(begin(cuts), end(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]