模板：

最小化：

  1. class Solution:
  2.     def minCost(self, n: int, cuts: List[int]) -> int:
  3.         cuts.sort()
  4.         cuts=[0]+cuts+[n]
  5.         m=len(cuts)
  6.         dp=[[float("inf")]*(m) for _ in range(m)]
  8.         dp[0][0] = 0
  9.         for i in range(1,m):
  10.             dp[i][i] = 0;
  11.             dp[i-1][i] = 0;
  13.         for l in range(m-2,-1,-1):
  14.             for r in range(l+1,m):
  15.                 for k in range(l+1,r):
  16.                     dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+cuts[r]-cuts[l])
  17.         return dp[0][m-1]

最大化：

  1. class Solution:
  2.     def maxCoins(self, nums: List[int]) -> int:
  3.         nums=[1]+nums+[1]
  4.         n=len(nums)
  5.         dp=[[0]*(n) for _ in range(n)]
  7.         for i in range(n-2,-1,-1):
  8.             for j in range(i+1,n):
  9.                 for k in range(i+1,j):
  10.                     dp[i][j]=max(dp[i][j],nums[i]*nums[k]*nums[j]+dp[i][k]+dp[k][j])
  11.         return dp[0][n-1]

K组合并：

  1. class Solution:
  2.     def mergeStones(self, stones: List[int], K: int) -> int:
  3.         n=len(stones)
  5.         if (n-1)%(K-1):return -1
  7.         prefix = [0] * (n+1)
  8.         for i in range(1,n+1): prefix[i] = stones[i-1] + prefix[i-1]
  10.         @functools.lru_cache(None)
  11.         def dp(i, j, m):
  12.             if (j - i + 1 - m) % (K - 1):
  13.                 return float("inf")
  14.             if i == j:
  15.                 return 0 if m == 1 else float("inf")
  16.             if m == 1:
  17.                 return dp(i, j, K) + prefix[j + 1] - prefix[i]
  18.             temp=float("inf")
  19.             for mid in range(i, j, K - 1):
  20.                 temp=min(temp, dp(i, mid, 1) + dp(mid + 1, j, m - 1) )
  21.             return temp
  22.         res = dp(0, n - 1, 1)
  23.         return res