python leetcode使数组变美的最小增量运算数，记忆化搜索和递推练习

今天闲着做了一道leetcode题目

1.题目：使数组变美的最小增量运算数

2.题解 

方法一：

class Solution:
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        n = len(nums)

        @cache
        def dfs(i, j):
            if i < 0:
                return 0
            res = dfs(i - 1, 0) + max(k - nums[i], 0)
            if j < 2:
                res = min(res, dfs(i - 1, j + 1))
            return res
        
        return dfs(n - 1, 0)

方法二：参考灵神的代码

class Solution:
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        f0 = f1 = f2 = 0
        for x in nums:
            inc = f0 + max(k - x, 0)
            f0 = min(inc, f1)
            f1 = min(inc, f2)
            f2 = inc
        return f0