397. Integer Replacement

Given a positive integer n and you can do operations as follow:

• If n is even, replace n with n/2.
• If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1

Example 2:

Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

S1: math

当n是奇数时只有当n+1能被四整除才选n+1，否则都是n-1 （3是例外）

    int integerReplacement(int n) {
       long num = n;  //转化为long防止n = INT_MAX时加以溢出
       int count = 0;
       while (num > 3) {
           if (num & 1) {
               if ((num >> 1) & 1) num++; //n + 1 可被4整除，即n以11结尾
               else num--;
           } else num >>= 1;
           count++;
       }
       return count + num - 1;
    }

S2: 记忆化搜索 space O(N)

    int integerReplacement(int n) {
        dp = vector<int>(n + 2, -1);
        dp[1] = 0;
        dfs(n);
        return dp[n];
    }

    int dfs(int n) {
        if (dp[n] >= 0) return dp[n];
        if (n & 1) dp[n] = min(dfs(n + 1), dfs(n - 1)) + 1;
        else dp[n] = dfs(n / 2) + 1;
        return dp[n];
    }
    vector<int> dp;