Day31力扣打卡

打卡记录

由子序列构造的最长回文串的长度（区间DP）

先将两个字符串合并，再仿照 最长回文子序列 的做法，从中间开始往外进行遍历，由于是两个字符串，在 最长回文子序列 的做法上需要满足 len(word1) < j 的条件答案。

class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        s = word1 + word2
        ans, n = 0, len(s)
        f = [[0] * n for _ in range(n)]
        max = lambda x, y: x if x > y else y
        for i in range(n - 1, -1, -1):
            f[i][i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1] + 2
                    if i < len(word1) <= j:
                        ans = max(ans, f[i][j])
                else: f[i][j] = max(f[i + 1][j], f[i][j - 1])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

多边形三角剖分的最低得分（区间DP）

先将问题分割为小问题，设 i, j, k 三点将多边形分为三块小多边形，k 为中间节点，类似于 Floyd 的算法思想。大佬的题解

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        n = len(values)

        f = [[0] * n for _ in range(n)]
        for i in range(n - 3, -1, -1):
            for j in range(i + 2, n):
                f[i][j] = min(f[i][k] + f[k][j] + values[i] * values[j] * values[k] 
                for k in range(i + 1, j))
        return f[0][n - 1]
1
2
3
4
5
6
7
8
9
10