Integer Replacement

这个题首先想到的就是动态规划去解，因为这里有个很明显的转移方程在里面，但是因为O(n)的时间复杂度超时了，就发现其实DP记录了很多用不到的中间值，而我们完全可以依照DP的原始过程即递归来求得解，下面是递归的代码，因为这里的递归树受到奇偶数的制约不会随着下潜急剧膨胀，所以可以认为这里时间复杂度基本上还是O(lgn)

class Solution(object):
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 1:
            return 0

        if n % 2 == 0:
            return 1 + self.integerReplacement(n / 2)
        else:
            return min(self.integerReplacement((n + 1) / 2) + 2, self.integerReplacement(n - 1) + 1)