给定一串数字和多个乘法运算符,可以计算的最高数字是多少？

Question

这是我的一个采访问题,我很尴尬地被它弄得很难过.想知道是否有人能想出答案并为它提供大的O符号.

Question: Given a string of numbers and a number of multiplication operators, 
          what is the highest number one can calculate? You must use all operators

你不能重新排列字符串.您只能使用乘法运算符来计算数字.

例如String = "312",1个乘法运算符

你可以做3*12 = 36或31*2= 62.后者显然是正确的答案.

Answer 1

我在这里假设所需的乘法运算符数m是作为问题的一部分给出的,以及数字的字符串s.

您可以使用表格方法(也称为"动态编程")解决此问题,其中O(m  | s | ²)乘以O(| s |)位数的数字.乘法的最佳计算复杂度是未知的,但是对于教科书乘法算法,这总体上是O(m  | s | ⁴).

(这样做是为了计算每个子问题由字符串和数字的尾部的答案米 '≤  米.有O(米 | 小号 |),例如子问题和解决每一个包括O(| 小号 |)的乘法长度为O(| s |)的数字.)

在Python中,您可以使用Python装饰器库中的@memoized装饰器对此进行编程:

@memoized
def max_product(s, m):
    """Return the maximum product of digits from the string s using m
    multiplication operators.

    """
    if m == 0:
        return int(s)
    return max(int(s[:i]) * max_product(s[i:], m - 1)
               for i in range(1, len(s) - m + 1))

如果您已经习惯了自下而上的动态编程形式,那么这个自上而下的表单可能看起来很奇怪,但事实上,@memoized装饰器将表保存在cache函数的属性中:

>>> max_product('56789', 1)
51102
>>> max_product.cache
{('89', 0): 89, ('9', 0): 9, ('6789', 0): 6789, ('56789', 1): 51102, ('789', 0): 789}

Answer 2

我发现上述DP解决方案很有帮助，但令人困惑。重复执行是有道理的，但是我想在一张表中完成所有操作而无需最后检查。我花了很长时间调试所有索引，因此我保留了一些解释。

回顾一下：

1. 将T初始化为大小为N（由于数字0..N-1）的k + 1（因为乘以0..k）。
2. 表T（i，j）=使用字符串的i + 1个第一位数字（由于零索引）和j乘积得出的最大乘积。
3. 基本情况：对于0..N-1中的i，T（i，0）= digits [0..i]。
4. 重复发生：T（i，j）= max _a（T（a，j-1）* digits [a + 1..i]）。即：将数字[0..i]划分为数字[0..a] *数字[a + 1..i]。并且由于这涉及到乘法，因此子问题的乘法较少，因此请在j-1处搜索表。
5. 最后，答案存储在T（所有数字，所有乘法）或T（N-1，k）。

复杂度为O（N ² k），因为对a的最大值为O（N），我们对每个数字（O（N））进行O（k）次。

public class MaxProduct {

    public static void main(String ... args) {
        System.out.println(solve(args[0], Integer.parseInt(args[1])));
    }

    static long solve(String digits, int k) {
        if (k == 0)
            return Long.parseLong(digits);

        int N = digits.length();
        long[][] T = new long[N][k+1];
        for (int i = 0; i < N; i++) {
            T[i][0] = Long.parseLong(digits.substring(0,i+1));
            for (int j = 1; j <= Math.min(k,i); j++) {
                long max = Integer.MIN_VALUE;
                for (int a = 0; a < i; a++) {
                    long l = Long.parseLong(digits.substring(a+1,i+1));
                    long prod = l * T[a][j-1];
                    max = Math.max(max, prod);
                }
                T[i][j] = max;
            }
        }
        return T[N-1][k];
    }
}