题解(1547):切棍子的最小成本(Python)"/>
LeetCode题解(1547):切棍子的最小成本(Python)
题目:原题链接(困难)
标签:动态规划
解法 | 时间复杂度 | 空间复杂度 | 执行用时 |
---|---|---|---|
Ans 1 (Python) | O ( M 3 ) O(M^3) O(M3) | O ( M 2 ) O(M^2) O(M2) | 908ms (57.63%) |
Ans 2 (Python) | |||
Ans 3 (Python) |
解法一:
class Solution:def minCost(self, n: int, cuts: List[int]) -> int:# 排序cuts并添加左右端点cuts.sort()cuts = [0] + cuts + [n]size = len(cuts)# 定义状态矩阵:dp[i][j] = 以i和j为端点的最小值dp = [[float("inf")] * size for _ in range(size)]for i in range(size - 1, -1, -1):for j in range(i, size):if i == j or i + 1 == j:dp[i][j] = 0for k in range(i + 1, j):dp[i][j] = min(dp[i][j], cuts[j] - cuts[i] + dp[i][k] + dp[k][j])return dp[0][-1]
更多推荐
LeetCode题解(1547):切棍子的最小成本(Python)
发布评论