LeetCode题解(1547)：切棍子的最小成本(Python)

题解(1547)：切棍子的最小成本(Python)"/>

LeetCode题解(1547)：切棍子的最小成本(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]