区间dp

灵茶山艾府视频

516. 最长回文子序列

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        f = [[0] * n for _ in range(n)]
        for i in range(n):
            f[i][i] = 1
        for l in range(2, n + 10):
            for i in range(n):
                j = i + l - 1
                if j >= n:
                    break
                if s[i] == s[j]:
                    f[i][j] = max(f[i][j], f[i + 1][j - 1] + 2)
                else:
                    f[i][j] = max(f[i + 1][j], f[i][j - 1])
        return f[0][n - 1]

1039. 多边形三角剖分的最低得分

状态转移函数：

加了@cache就是记忆化了...太叼了
dfs是自顶向下，这个会比较好想

class Solution:
    def minScoreTriangulation(self, v: List[int]) -> int:
        n = len(v)
        @cache
        def dfs(i, j):
            if i + 1 == j:
                return 0
            res = 1e9
            for k in range(i + 1, j):
                res = min(res, dfs(i, k) + dfs(k, j) + v[i] * v[j] * v[k])
            return res
        return dfs(0, n - 1)

# 状态有O(n^2)个，计算每个状态需要O(n)，所以总体复杂度是O(n^3)

自底向上的递推，用len从小到大，确定i之后，右端点j = i + len - 1。
跟视频里灵神写法不一样

class Solution:
    def minScoreTriangulation(self, v: List[int]) -> int:
        n = len(v)
        f = [[0] * n for _ in range(n)]

        for l in range(3, n + 2):
            for i in range(n):
                j = i + l - 1
                if j >= n:
                    break
                f[i][j] = 1e9
                for k in range(i + 1, j):
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j] + v[i] * v[j] * v[k])
        return f[0][n - 1]