本文共 1389 字，大约阅读时间需要 4 分钟。

题目地址：

给定一个正整数$k$，从$0$出发，每次可以将数加$1$或者乘以$2$，问几次操作可以使得$0$变成$k$。

法1：动态规划。设$f[i]$是从$0$经过多少步可以变成$i$，则$$f[i]=1+\min \{$$

public class Solution {       /**     * @param k: integer k     * @return: minimum number of operations that change 0 to k     */    public int numberChange(int k) {           // write your code here        int[] dp = new int[k + 1];        for (int i = 1; i <= k; i++) {               dp[i] = 1 + dp[i - 1];            if (i % 2 == 0) {                   dp[i] = Math.min(dp[i], 1 + dp[i / 2]);            }        }                return dp[k];    }}

时空复杂度$O(k)$。

法2：相当于问，每次允许对$k$进行减$1$或者除以$2$的操作，多少次能到$0$。容易看出如果$k$是偶数，则让其除以$2$，否则让其减去$1$，最后数一下步数即可。至于证明，只需看到对于任意别的方案，进行了相同步数之后，上面贪心的方法得数一定是更小的。代码如下：

public class Solution {       /**     * @param k: integer k     * @return: minimum number of operations that change 0 to k     */    public int numberChange(int k) {           // write your code here        int res = 0;        while (k > 0) {               if (k % 2 == 0) {                   k /= 2;            } else {                   k--;            }                        res++;        }                return res;    }}

时间复杂度$O(\log k)$，空间$O(1)$。

转载地址：http://lgcs.baihongyu.com/