使整数变为 0 的最少操作次数

题目

1611. 使整数变为 0 的最少操作次数

---

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

• 翻转 n 的二进制表示中最右侧位（第 0 位）。
• 如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

示例 1：

输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。

示例 2：

输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。

提示：

• 0 <= n <= 10^9

题解

方法一：

思路

九连环解法

我们知道解九连环第1环可以在杆上任意上下，第i环的上下需要保证i-1环在杆上，1到i-2环都在杆下。如果将题目给出的数字转为二进制，可以将0看作在拆下的环，1看作上好的环。

先推一下九连环的状态转移方程。现在给出长度为n的全1字符串，也就是一个n连环。设dp[n]是解开这个n连环的步数。显然需要解开前n-2个环才能使得第n个环解下，在解下第n个环后再将前n-2个环上好那么问题就转换成了解n-1连环了。所以dp[n] = dp[n-2]*2+dp[n-1]+1。可以初始化dp[1] = 1,dp[2]= 2，剩余对于n>2的dp[n]可以通过递推式得到。

但是题目给出的是一个解了一部分的n连环。在我一番思考后发现：

如果第i个环上好的，假设从1到i-1个环都是取下的，那么我要拆下这个环就要上好前i-1个环然后解一个i连环，就是所需要的步数是dp[i]+dp[i-1]，然而假设可能不成立，前i-1个环可能有没取下的环。但前面的环实际上是为我们解开第i个环节省了步数。

想到这里可以定义d[i] 为解开前i个环的最小步数

如果第i个环是上好的，d[i] = dp[i]+dp[i-1]-d[i-1]

如果第i个环是拆下的，d[i] = d[i-1]

答案就是dp[sz], sz是给出数字的二进制长度。

代码

class Solution {
public:
    string s;
    int ring[32];
    int dfs(int p) {
        if (p==0) return 0;
        if (s[p-1] == '1') return ring[p]+ring[p-1]-dfs(p-1);
        else return dfs(p-1);
    }
    int minimumOneBitOperations(int n) {
        ring[1] = 1;
        ring[2] = 2;
        for (int i=2; i<32; i++) {
            ring[i] = ring[i-1]+ring[i-2]*2+1;
        }
        // for (int i=0; i<32; i++) {
        //     cout << ring[i] << " ";
        // }cout << endl;
        while (n) {
            // cout << n%2 << " ";
            s.push_back(n%2+'0');
            n>>=1;
        }
        return dfs(s.size());
    }
};