在x大神统治的（一维）宇宙中，他不允许任何反抗者。有一天他听说有个叫y的傻叉打算闹独立，于是决定亲自前去消灭他。x位于原点，y位于坐标为n处的。x的战舰使用超空间跃迁，由于设计蛋疼，跃迁的方式十分奇怪。具体说，第一次只能跃迁到坐标为1处，以后每次跃迁的终点坐标必须为之前某两次（可以相同）跃迁终点的坐标之和。并且只能向前跃迁，不能掉头。x想知道至少要跃迁几次才能到达y处
输入输出格式
输入格式
一个正整数n（2<=n<=300）
输出格式
一个正整数，表示至少需要跃迁几次
输入输出样例
输入样例#1:
5
输出样例#1:
4

#include<bits/stdc++.h>
using namespace std;
int dfs(int num) {
    if(num!=0){ 
        if(num%2==0) 
            return 1+dfs(num/2);
        else 
            return 1+dfs(num-1);     
    }
    return 0;
}

signed main(){
    int n;
    cin>>n;
    cout<<dfs(n);
    return 0;
}

69分

input

43
output

8
myOutput

9