LeetCode1130-DP

发表于

leetcode 1130

思路:

dp[i,j]=min(dp[i,k]+dp[k+1,j]+max(arr[i:k+1])*max(arr[k+1:j+1])

因此，直接使用dp函数求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        a = [[0] * len(arr) for i in range(len(arr))]

        def dp(i, j):
            if i == j:
                return 0
            if a[i][j] != 0:
                return a[i][j]
            res = float('inf')
            for k in range(i, j):
                res = min(res, dp(i, k) + dp(k + 1, j) + max(arr[i:k + 1]) * max(arr[k + 1:j + 1]))
            a[i][j] = res
            return res

        return dp(0, len(arr) - 1)

反思：因为很久没有做leetcode的题目了，结果这道这么简单的题都没有做出来，是时候反省一下自己了。为什么最近自己总是想着玩，没有认真对待自己的代码。对于coder而言，代码就是自己的尊严呀！