首页 > 试题广场 >

小招喵跑步

[编程题]小招喵跑步
  • 热度指数：11771 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小招喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3种走法，分别是：
1.数轴上向前走一步，即n=n+1 
2.数轴上向后走一步,即n=n-1 
3.数轴上使劲跳跃到当前点的两倍，即n=2*n
现在小招喵在原点，即n=0，它想去点x处，快帮小招喵算算最快的走法需要多少步？

输入描述:
小招喵想去的位置x


输出描述:
小招喵最少需要的步数
示例1

输入

3

输出

3
算法知识视频讲解
添加回答
Python3
迷人的小松鼠G了头像 迷人的小松鼠G了 
x = int(input())
if x<0: x=-x
dp = [0]*(x+2)
dp[1] = 1
for i in range(2,x+1):
    if i%2 == 0:
        dp[i] = dp[i//2] + 1
    else:
        dp[i] = min(dp[i-1]+1, dp[(i+1)//2]+2)
print(dp[x])

发表于 2025-03-20 10:33:06 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 动态规划 2018 招商银行信用卡中心 Java工程师
上传者：小小
难度：
1条回答 12632浏览

热门推荐

通过挑战的用户

查看代码

相关试题

小招喵跑步

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号