Broken Calculator

给两个数字, 给一组操作, 乘2或者减1, 求能不能从start到target.

这题吧, 有点意思, 因为用greedy做, 所以找greedy的条件的时候, 会发现因为我们要最多的乘除, 但是乘法无法确定一定在最优解的路径上. 而除法可以通过判断是不是target % 2 == 0 可以确定在答案路径上, 所以则选用从target 到 start的除+加.

class Solution {
    public int brokenCalc(int startValue, int target) {
        if(startValue >= target)
            return startValue - target;
        if(target % 2 == 0) // best option (greed)
            return 1 + brokenCalc(startValue, target / 2);
        else
            return 1 + brokenCalc(startValue, target + 1);
    }
}