偶然在网上看到了一个题目,看了看视频和评论,感觉挺有意思,记录一下。
只通过+1和×2两种操作,最少几次能把0变成20240701?_哔哩哔哩_bilibili
题目:只通过+1和×2两种操作,最少几次能把0变成20240701?
代码:
n = 20240702
def dpSolution(n):
lst = [-1] * (n + 10)
lst[0] = 0
for i in range(1, n + 1):
if i % 2:
lst[i] = lst[i - 1] + 1
else:
lst[i] = min(lst[i - 1], lst[i // 2]) + 1
return lst[n]
def binSolution(n):
return bin(n).count('1') + n.bit_length()-1
# print(dpSolution(n))
print(binSolution(n))