python: @lru_cache(None) 데코레이터

재귀함수 위에 @lru_cache(None) 데코레이터를 사용하면  함수가 반환하는 값을 메모이제이션(memoization)할 수 있다.

 

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        s = [int(i) for i in s]+[1]
        
        @lru_cache(None)
        def dp(i, k):
            if i==-1: return 0
            return min([dp(i-1, j)+int(k!=s[i]) for j in range(k+1)])
        
        return dp(len(s)-1,1)