Integer Replacement LeetCode solution in Python

1
# Runtime: 42 ms (Top 77.23%) | Memory: 14 MB (Top 29.19%)
2

3

4
class Solution:
5
    def integerReplacement(self, n: int) -> int:
6
        dp = {}
7

8
        def dfs(num):
9
            if num == 1:
10
                return 0
11

12
            if num in dp:
13
                return dp[num]
14

15
            # if num is even, we have only one option -> n / 2
16
            even = odd = 0
17
            if num % 2 == 0:
18
                even = 1 + dfs(num // 2)
19
            else:
20
                # if num is odd, we have two option, either we increment the num or decrement the num
21
                odd1 = 1 + dfs(num - 1)
22
                odd2 = 1 + dfs(num + 1)
23
                # take the min of both operation
24
                odd = min(odd1, odd2)
25

26
            dp[num] = even + odd
27
            return dp[num]
28

29
        return dfs(n)