964. Least Operators to Express Number

Version #2 Dijastra[TODO]


Version #1 Memorized DFS
最重要的是要掌握 如何用一个x的多项式，组成target？
1 '/' 一定是多余的，因为 没有必要进行任何形式的 x * x / x 的冗余操作
2 '/' 只出现在我们需要1的情况下 1 == 'x / x'
3 多项式表示为arget = c0*x^0 + c1*x^1 + c2*x^2 + ...
                 + cn*x^(log(target) / log(x)) + cn+1*x^(log(target) / log(x) + 1)
其中的c 在 (+/- x)
4 避免成环就是要避免重复搜索
case 1 不会造成重复搜索， 因为 target - x^k永远只能越来越小
case 2 如果x^(k+1) - target 比target大或相等，就无法收敛，所以要避免这种情况

写了一个bug
出现在当我们需要 c0 * x^0 的时候
因为我没没有办法以任何形式表示 x^0，所以只能用 x/x 代替 x^0
根据其他k的规律， x^2 = x * x  -> 1 = k-1
                                   x^ 3 = x * x * x -> 2 = k-1
在这里是违反的，因为 x^0 -> 1
所以要特殊情况特殊讨论


Time O(log target)

26.14 %
class Solution {
    public int leastOpsExpressTarget(int x, int target) {
        // target = c0*x^0 + c1*x^1 + c2*x^2 + ...
        //          + cn*x^(log(target) / log(x)) + cn+1*x^(log(target) / log(x) + 1)
        Map<Integer, Integer> visited = new HashMap<>();
        visited.put(0, 0); // no ops needed for 0
        visited.put(1, 1); // 1 -> x/x -> 1 op for 1
        return dfs(x, target, visited);
    }
   
    private int dfs(int x, int target, Map<Integer, Integer> visited) {
        if (visited.containsKey(target)) return visited.get(target);
        int k = (int) Math.floor(Math.log(target) / Math.log(x));
        // when k == 0, we can't make 3^0
        int p = (int) Math.pow(x, k);
        if (p == target) { // x*x*x -> 2 ops
            visited.put(target, k - 1);
            return k - 1;
        }
        // 1st choice -> target - x^k
        int min = (k == 0 ? 2 : k) + dfs(x, target - p, visited);
        // 2nd choice -> x^(k+1) - target -> we have to guarantee that x^(k+1) - target < target
        if (p * x - target < target) {
            min = Math.min(min, k + 1 + dfs(x, p * x - target, visited));
        }
        // we don't minus 1 for both case 1 and 2
        // because we need an extra (+/-) to combine current result to its subproblem's result
        visited.put(target, min);
        return min;
    }
}