问题描述如下，给定任意一个正整数，只允许两种操作，+1或者x2，问从1到这个数字最短需要多少步。
比如给定10，最短步数就是4步，如上图所示，
这个题其实和leetcode爬楼梯是一个道理，也是有递归和非递归写法的
递归求解：
首先看一下递归公式，达到某个数字n的步数，等于一步之远的数字的步数+1，这个一步之远可以是加一操作的，也可以是翻倍操作的，即
T
(
n
−
1
)
T(n-1)
T
(
n
−
1
)
或者
T
(
n
/
2
)
T(n/2)
T
(
n
/
2
)
所以状态公式就出来：
T
(
n
)
=
1
+
m
i
n
(
T
(
n
−
1
)
,
T
(
n
/
2
)
)
T(n) = 1+min(T(n-1), T(n/2))
T
(
n
)
=
1
+
m
i
n
(
T
(
n
−
1
)
,
T
(
n
/
2
)
)
代码如下：
def c(n):
if n==1:
return 0
elif n%2!==0:
return 1 + c(n-1)
else:
return 1 + min(c(n-1), c(int(n/2)))
这里特殊情况是如果n是奇数的时候，他就只有+1这种操作能够达到。
递归肯定是会有重复计算的，所以非递归解法通过动态规划的方式，避免了重复计算。
非递归求解
初始状态，当n=1时，step=0，n=2时，step=1， n=3时，step=2.
def dp(n):
if n<=3:
return n-1
else:
T=[0 for i in range(n+1)]
T[1],T[2],T[3]=0,1,2
for i in range(4, len(T)):
if i%2!=0:
T[i] = 1 + T[i-1]
else:
T[i] = 1 + min(T[i-1], T[int(i/2)])
return T[n]