题目：

假设有如下操作，偶数则除以2，奇数可以加1或减1，那么问给定某个数，让它变成1需要的最少操作是多少步？

思路：

1、动态规划：

递推方程：

if n&1==1  dp[n]=min(dp[n-1]+1,dp[(n+1)/2]+1)

if n&1==0  dp[n]=dp[n/2]+1

初始状态：

dp[1]=1;

dp[2]=1;

2、回溯法

通过递归方式枚举可能走的路径，在过程中通过剪枝的方式降低复杂度。

代码：

#include
     
      #include
      
       #include
       
        using namespace std;int minsteps_dp(int n){    vector
        
          steps(n+1,0);    steps[0]=0;    steps[1]=0;    steps[2]=1;    for(int i=3;i<=n;i++){        if(i&1==1)            steps[i]=min(steps[i-1]+1,steps[(i+1)/2]+1);        else            steps[i]=steps[i/2]+1;    }    return steps[n];}void minsteps_backtrack(int n,int step,int &minsteps){    if(n==1){        minsteps=min(step,minsteps);        return;    }    if(step>minsteps)        return;    if(n&1){        minsteps_backtrack(n-1,step+1,minsteps);        minsteps_backtrack(n+1,step+1,minsteps);    }    else        minsteps_backtrack(n/2,step+1,minsteps);}int main(){    int n;    int minsteps=0;    while(cin>>n){        cout<
         
          <