求从N到1的最少操作次数（仅允许加减1或除2）

题目等价于：在只允许加、减1或乘2的前提下，求从1变到N的最少操作次数。

 

分析：任意一个中间数m，若m为偶数，则可能由m-1加1得到，或是由m/2乘2得到；若m为奇数，则可能由m-1加1得到，或是由(m+1)/2经过乘2再减1得到，故可得递推式：

 

n为偶数： f(n) = min{f(n-1)+1, f(n/2)+1}

n为奇数： f(n) = min{f(n-1)+1, f((n+1)/2)+2}

初始值： f(0)=f(1)=0

 

public static int minOperation(int N) { int[] dp = new int[N+1]; dp[0] = dp[1] = 0; for(int i=2; i<=N; i++) { if(i%2==0) { dp[i] = Math.min(dp[i/2]+1, dp[i-1]+1); } else { dp[i] = Math.min(dp[i-1]+1, dp[(i+1)/2]+2); } } return dp[N]; }