LeetCode/solutions/397. Integer Replacement.md

# [397. Integer Replacement](https://leetcode.com/problems/integer-replacement/)

# 思路
给定一个正整数n，然后让我们通过变换变为1，求最小的变换步数。变换定义如下：
* 如果n是偶数，变为n/2；
* 如果n是奇数，可以变为n+1或者n-1。

所以，
* 若n为偶数，`integerReplacement(n) = 1 + integerReplacement(n >> 1);`
* 若n为奇数，`integerReplacement(n) = 1 + min(integerReplacement(n - 1), 1 + integerReplacement((n >> 1) + 1));`。
> 注意若n为奇数那么`((n+1) >> 1) == (n >> 1) + 1`，前者当n为INT_MAX时会溢出而后者不会。

一开始我想到用动归，但是发现从前往后更新dp时会很耗时，因为做了很多不必要的计算，所以我们应该从后往前更新dp，也即用递归。
另外，我们可以用一个hash表cache来存放已经计算出来的值避免重复计算。

# 代码
``` C++
class Solution {
private:
    unordered_map<int, int>cache;
public:
    int integerReplacement(int n) {
        if(n < 2) return 0;
        
        if(cache.count(n)) return cache[n];
        
        int res = 0, n_back = n;
        if(n & 1)
            res = 1 + min(integerReplacement(n - 1), 
                          1 + integerReplacement((n >> 1) + 1));
        else{
            // 不断除2直到结果是奇数
            while(!(n & 1)){
                res += 1;
                n >>= 1;
            }
            res += integerReplacement(n);
        }
        cache[n_back] = res;
        return res;
        
    }
};
```