当前位置：首页 > news >正文

动态规划与位运算：数字归零的最少操作策略

news 2026/8/10 11:39:23

1. 问题背景与核心思路

第一次看到这个题目时，我正坐在星巴克刷LeetCode周赛。题目要求计算将任意非负整数变为0所需的最少操作次数，允许的操作只有两种：要么减1，要么除以2（仅当数字为偶数时）。这让我想起了计算机科学中经典的"二进制表示"问题。

动态规划(DP)之所以适合解决这个问题，是因为它具有两个关键特征：

最优子结构：当前数字的最优解依赖于更小数字的最优解
重叠子问题：计算较大数字时会反复用到较小数字的解

举个例子，数字8的最优解路径是：8→4→2→1→0（共4步），而暴力穷举所有可能路径显然效率太低。DP通过存储中间结果避免了重复计算，这正是它的精妙之处。

2. 基础解法实现

2.1 递归解法（自顶向下）

我们先从最直观的递归解法开始，虽然效率不高，但能清晰展示问题本质：

def minOperations(n): if n == 0: return 0 if n % 2 == 0: return 1 + minOperations(n // 2) else: return 1 + minOperations(n - 1)

这个解法的时间复杂度是O(n)，空间复杂度O(n)（递归栈深度）。当n=1e5时就会栈溢出。我在第一次提交时就因为这个吃了TLE（Time Limit Exceeded）的亏。

2.2 记忆化搜索优化

添加记忆化可以避免重复计算：

memo = {} def minOperations(n): if n in memo: return memo[n] if n == 0: return 0 if n % 2 == 0: memo[n] = 1 + minOperations(n // 2) else: memo[n] = 1 + minOperations(n - 1) return memo[n]

这样时间复杂度降为O(logn)，因为每个数字只计算一次。但实际测试发现，当n=1e6时，递归深度仍然可能导致栈溢出。

3. 标准动态规划解法

3.1 自底向上迭代

更稳妥的方法是使用DP数组迭代：

def minOperations(n): dp = [0] * (n + 1) for i in range(1, n + 1): if i % 2 == 0: dp[i] = dp[i // 2] + 1 else: dp[i] = dp[i - 1] + 1 return dp[n]

这个版本时间复杂度O(n)，空间复杂度O(n)。对于n=1e7也能快速计算，但会消耗约40MB内存（每个int4字节）。

3.2 空间优化技巧

观察到当前状态只依赖前一个状态或一半状态，可以优化空间：

def minOperations(n): res = 0 while n > 0: if n % 2 == 0: n = n // 2 else: n -= 1 res += 1 return res

这个优化版本空间复杂度降为O(1)，时间复杂度仍然是O(logn)，因为每次操作至少将数字减半。

4. 数学规律与位运算

4.1 二进制视角分析

将数字表示为二进制时，操作对应：

减1：将最低位的1变为0（如1011→1010）
除以2：右移一位（如1010→101）

最优策略是：遇到1就减1（产生进位），遇到0就右移。因此操作次数等于二进制中1的个数加上最高位位数减1。

4.2 位运算实现

基于这个发现可以得到更优解：

def minOperations(n): res = 0 while n: res += 1 + (n & 1) n >>= 1 return max(res - 1, 0)

这个算法的时间复杂度O(logn)，但常数时间更优，实测比DP快3-5倍。

5. 不同语言实现对比

5.1 C++实现

int minOperations(int n) { int res = 0; while(n) { res += (n % 2) ? 2 : 1; n = (n % 2) ? n - 1 : n / 2; } return max(res - 1, 0); }

5.2 Java实现

public int minOperations(int n) { int res = 0; while (n > 0) { res += (n % 2 == 0) ? 1 : 2; n = (n % 2 == 0) ? n / 2 : n - 1; } return Math.max(res - 1, 0); }

6. 常见错误与调试技巧

6.1 边界条件处理

新手常犯的错误包括：

忽略n=0的情况直接返回1
对n=1时的处理不当
整数溢出（当n接近2^31时）

重要提示：所有DP问题都必须先考虑边界条件！

6.2 性能优化实战

我在LeetCode测试时发现：

当n=1e9时，递归解法直接爆栈
基础DP解法会超时（Python）
位运算解法仅需0.3ms

测试用例建议：

test_cases = [ (0, 0), (1, 1), (2, 2), (3, 3), (4, 3), (5, 4), (8, 4), (123456, 22) ]

7. 实际应用场景

这个问题看似简单，但它的变种出现在：

计算机组成原理中的指令优化
网络协议中的计数器设计
游戏开发中的技能冷却计算
区块链中的难度调整算法

比如在Redis的过期键删除策略中，就使用了类似的渐进式操作来避免服务器卡顿。

8. 进阶挑战与扩展

8.1 操作代价变化问题

如果不同操作代价不同（如减1耗时为2，除以2耗时为1），如何修改算法？

def minOperations(n, cost_sub=2, cost_div=1): dp = [0]*(n+1) for i in range(1,n+1): if i%2 == 0: dp[i] = min(dp[i-1]+cost_sub, dp[i//2]+cost_div) else: dp[i] = dp[i-1] + cost_sub return dp[n]

8.2 多操作选项问题

如果增加操作选项（如可以除以3），解决方案会变得复杂，需要结合BFS和DP：

from collections import deque def minOperations(n): visited = set() q = deque([(n, 0)]) while q: num, steps = q.popleft() if num == 0: return steps if num in visited: continue visited.add(num) q.append((num-1, steps+1)) if num % 2 == 0: q.append((num//2, steps+1)) if num % 3 == 0: q.append((num//3, steps+1)) return -1