最近两个月力扣困难题不再落下，打卡全满勤，激发了持续刷题的斗志。这里将持续记录打卡过程中的难题和面试八股。
2023/4/2 1039. 多边形三角剖分的最低得分
题目大意：
多边形每个节点有一个数值，将多边形三角剖分，得分为所有三角形节点乘积之和。求三角剖分后的最低得分。
做题评价：
虽然中等题，但没能第一时间做出来。需要熟练掌握动态规划，避免先入为主而被错误方法引导。
解题过程：
1）三角剖分有一个经典的计数问题，即求凸多边形的三角剖分方案数。该问题很容易通过固定两个端点（如0和n-1)，枚举中间节点k，将问题转化为两个多边形(区间0-k)和(区间k-n-1)的子问题。这个问题的解是卡特兰数。
2）先入为主陷入了错误的想法：由于上面问题结果的规模是指数增长，我以为无法通过动态规划求解出每一种方案来找到全局最小值，于是不断尝试用贪心法：
- 重复选择值最小的两个节点：需要节点不相邻，这个改对甚至通过了92 / 94 个测试用例。
- 重复选择值相乘最小的两个节点
- 交了三次，分别得到一些例外情况 [3-6-1-2] 和 [2-3-7-3]
3）重新思考子问题，即如何表示一个多边形的最低得分。
- 用dp[i][j] 表示 i~j 这些节点围成的多边形的最优解
- 初始化
dp[i][i+1] = 0(两个节点）
dp[i][i+2] = v[i]*v[i+1]*v[i+2]（三个节点） - 由边数从小到大遍历3<=l<n，计算 dp[i][i+l]，j = i+l
对每个 dp[i][j] 枚举中间节点 i<k<j，稍加推导，易得
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j] + values[i]*values[k]*values[j]) - 返回答案 dp[0][n-1]
ChatGPT对以上记录的评价
您的博客记录已经很不错了，总体上清晰地概括了这道题目的背景和解题思路，并且提到了自己在解题过程中遇到的问题和困惑，这对读者来说非常有帮助。
以下是一些可以改进的地方：
对题目的描述可以更加详细和准确。例如，可以提到多边形是凸多边形，每个节点的数值都是正整数等等。这样有助于读者更好地理解题目。
在解题过程中，建议更加详细地讲解每一步的推导过程和原因，这样读者可以更清晰地理解算法的实现。
最后，可以在博客记录中提供代码实现，以方便读者查看和参考。同时，可以加入一些具体的实例来说明算法的使用和效果，这样读者可以更好地理解和掌握算法。
希望以上建议可以帮助到您，祝您写作愉快！
ChatGPT润色修改版
题目描述：
给定一个凸多边形，每个节点有一个正整数数值。将多边形进行三角剖分，并计算所有三角形上节点数值的乘积之和。求剖分后的最低得分。
解题过程：
问题分析
- 首先，我们需要明确问题的规模，即输入数据的范围和结果的规模，以便选择合适的算法。
在这道题目中，多边形的节点数范围是 [3,50]，每个节点的数值是正整数，结果的规模取决于多边形的三角剖分方案数，理论上可能会非常大，但是我们只需要求得最低得分，因此不必考虑具体的结果数值。 - 其次，我们需要考虑如何表示问题的子问题，即如何表示一个多边形的最低得分。
我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从节点 i 到节点 j 形成的多边形的最低得分。则所求答案即为 dp[0][n-1]。
动态规划解法
接下来，我们考虑如何利用动态规划求解问题。
-
首先，对于一个只有两个节点的多边形，它的最低得分显然为 0，因为它没有三角形可以构成。因此，我们可以初始化 dp[i][i+1] = 0。
-
接下来，我们考虑多边形节点数大于 2 的情况。我们可以按照多边形边数递增的顺序进行遍历，对于每个边数，我们枚举这个多边形中所有可能的三角剖分方案，并找到最低得分。
-
具体地，我们枚举中间节点 k，将多边形分成两个子多边形 [i,k] 和 [k,j]，计算它们的最低得分，再加上它们之间的三角形的得分
values[i]*values[k]*values[j]，即可得到总得分。
我们可以用以下公式表示：
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i]*values[k]*values[j])其中，i<k<j。 -
最后，我们返回 dp[0][n-1] 作为答案。
代码实现
def minScoreTriangulation(values):
n = len(values)
dp = [[0] * n for _ in range(n)]
for d in range(2, n):
for i in range(n - d):
j = i + d
dp[i][j] = float('inf')
for k in range(i + 1, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i]*values[k]*values[j])
return dp[0][n-1]
其中，values 是一个长度为 n 的数组，表示多边形每个节点的数值。函数返回值为三角剖分后的最低得分。
该算法的时间复杂度为 O(n^3)，空间复杂度为 O(n^2)。
需要注意的是，该算法使用了动态规划，需要了解动态规划的基本概念和思想。同时，该算法也需要您了解多边形的三角剖分以及节点乘积之和的概念。
（长期更新）
标签：得分,面试题,多边形,剖分,全记录,values,打卡,节点,dp From： https://www.cnblogs.com/izcat/p/17277143.html