397.整数替换

https://leetcode-cn.com/problems/integer-replacement/

一、dp

用dp[n]表示n变为1的最小操作次数，易知当n为偶数，只有一个来源dp[n] = dp[n/2]+1

当n为奇数，有两个来源：dp[n] = min(dp[n-1], dp[n+1]) + 1

class Solution:
    def integerReplacement(self, n: int) -> int:
        dp = [n] * (n+2)	#0号不用，i从1到n，多出一个n+1防止计算i+1时越界
        dp[1] = 0
        dp[2] = 1

        for i in range(3, n+1):
            if i % 2:
                dp[i] = min(dp[i-1], dp[i+1]) + 1
            else:
                dp[i] = dp[i//2] + 1
            if 2*i < n+2:	#每轮把2*i也算出来
                dp[2*i] = dp[i] + 1
        return dp[n]

然而超时

改进

其实没必要把1~n的次数都计算出来，只需要计算路径上情况的即可

class Solution:
    # @functools.lru_cache
    def integerReplacement(self, n: int) -> int:
        if n == 1:	#递归出口
            return 0
        if n % 2 == 0:
            return 1 + self.integerReplacement(n // 2)
        else:
            return 1 + min(self.integerReplacement(n+1), self.integerReplacement(n-1))