397. Integer Replacement.md

397. 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来存放已经计算出来的值避免重复计算。

代码

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;
        
    }
};