华为OD机试E卷 - 分糖果 Java题解

动态规划解法：

public static int minSteps(int candies) {
        int[] dp = new int[candies + 1]; //定义dp数组的大小为candies+1
        Arrays.fill(dp, Integer.MAX_VALUE); //填充数组为最大值
        if (candies <= 1) {                 //判断极端情况，为1 的时候返回0
            return 0;
        }
        dp[0] = 0;  //给dp数组的前两位赋值
        dp[1] = 0;
        for (int i = 2; i <= candies; i++) {
            if (i % 2 == 0) { //如果为偶数的时候，分糖果的时候的等式如下
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            } else {  //非偶数的糖果分的方式为 Math.min方法里的dp等式，这里加了两次1的原因是 放入或取出糖果都记为一次
                dp[i] = Math.min(dp[i], Math.min(dp[(i + 1) / 2], dp[(i - 1) / 2]) + 1) + 1;
            }
        }
        //System.out.println(Arrays.toString(dp)); //输出dp数组
        return dp[candies];
    }

递归解法：

private static int minSteps(long candies) {
        //递归出口条件
        if (candies <= 1) {
            return 0;
        }
        long halfCandies = candies / 2;
        if (candies % 2 == 0) { //判断是否是偶数 ，如果是偶数的话，进入下一层递归并对返回值+1记录step
            return minStepsHelper(halfCandies) + 1;
        } else { //糖果为奇数的情况，取出或放入
            return Math.min(minStepsHelper(candies + 1), minStepsHelper(candies - 1)) + 1;
        }
    }