老顶级编码器之谜：通过插入 + 来生成数字

Question

我正在考虑这个topcoder问题。

给定一串数字，找到该字符串等于某个目标数字所需的最少加法次数。每次添加都相当于在数字字符串中的某处插入一个加号。插入所有加号后，照常计算总和。

例如，考虑“303”和目标总和为 6。最佳策略是“3+03”。

我会用蛮力解决这个问题，如下：

for each i in 0 to 9 // i -- number of plus signs to insert
  for each combination c of i from 10
    for each pos in c // we can just split the string w/o inserting plus signs
      insert plus sign in position pos 
    evaluate the expression
    if the expression value == given sum
      return i

这有意义吗？从性能的角度来看它是否是最佳的？

...

好吧，现在我发现动态编程解决方案会更有效。然而，如果所提出的解决方案有意义的话，那就很有趣了。

Answer 1

这当然不是最佳的。例如，如果给定字符串“1234567890”并且目标是三位数，则您知道必须将该字符串拆分为至少四个部分，因此不需要检查 0、1 或 2 次插入。此外，目标还限制了允许插入位置的范围。这两点对于短弦的影响很小，但对于较长的弦可能会产生巨大的影响。不过，我怀疑有一种更好的方法，有点 DP 的味道。

Answer 2

我还没有考虑太多，但如果你向下滚动，你可以看到比赛的链接，从那里你可以看到求解器的解决方案。这是 C# 中的一个。

using System; 
using System.Text; 
using System.Text.RegularExpressions; 
using System.Collections; 

public class QuickSums { 
    public int minSums(string numbers, int sum) { 
        int[] arr = new int[numbers.Length]; 
    for (int i = 0 ; i < arr.Length; i++)       
      arr[i] = 0; 

    int min = 15; 

    while (arr[arr.Length - 1] != 2)     
    { 
      arr[0]++; 
      for (int i = 0; i < arr.Length - 1; i++) 
        if (arr[i] == 2)  
        { 
          arr[i] = 0; 
          arr[i + 1]++; 
        } 

      String newString = ""; 
      for (int i = 0; i < numbers.Length; i++) 
      { 
        newString+=numbers[i]; 
        if (arr[i] == 1) 
          newString+="+"; 
      } 

      String[] nums = newString.Split('+'); 
      int sum1 = 0; 
      for (int i = 0; i < nums.Length; i++) 
        try  
        { 
          sum1 += Int32.Parse(nums[i]); 
        } 
        catch 
        { 
        } 

      if (sum == sum1 && nums.Length - 1 < min) 
        min = nums.Length - 1; 
    } 

    if (min == 15) 
      return -1; 

    return min; 
  } 

} 

Answer 3

因为输入长度很小（10），所以所有可能的方式（可以通过长度为10的简单二进制计数器找到）都很小（2^10 = 1024），所以你的算法足够快并返回有效结果，并且IMO有不需要改进它。

总之，直到您的解决方案在时间、内存和其他给定限制下正常工作之前，无需进行微观优化。例如，akappa 提供的这种情况可以用 DP 来解决，就像两部分问题中的 DP 一样，但是当你的算法很快时，就不需要这样做，并且可能会添加一些大常量或使代码不可读。

我只提供一次字符串的解析数字（在长度为 10 的数组中），以防止过多的字符串解析，并且只需使用 a*10^k + ... （您也可以计算 10^k for k=0.. 9 在启动时并保存其值）。

Answer 4

我认为这个问题类似于矩阵链乘法问题，我们必须为最小乘法加上大括号。这里的大括号代表“+”。所以我认为它可以通过类似的 dp 方法来解决..将尝试实现它。

Answer 5

动态规划：

public class QuickSums {

public static int req(int n, int[] digits, int sum) {

    if (n == 0) {
        if (sum == 0)
            return 0;
        else
            return -1;
    } else if (n == 1) {
        if (sum == digits[0]) {
            return 0;
        } else {
            return -1;
        }
    }

    int deg = 1;
    int red = 0;

    int opt = 100000;
    int split = -1;

    for (int i=0; i<n;i++) {
        red += digits[n-i-1] * deg;

        int t = req(n-i-1,digits,sum - red);
        if (t != -1 && t <= opt) {
            opt = t;
            split = i;
        }
        deg = deg*10;
    }

    if (opt == 100000) 
        return -1;
    if (split == n-1) 
        return opt;
    else
        return opt + 1;

}

public static int solve (String digits,int sum) {
   int [] dig = new int[digits.length()];
   for (int i=0;i<digits.length();i++) {
       dig[i] = digits.charAt(i) - 48;
   }

    return req(digits.length(), dig, sum);
}


public static void doit() {
    String digits = "9230560001";
    int sum = 71;

    int result = solve(digits, sum);
    System.out.println(result);
}

Answer 6

似乎为时已晚..但请阅读此处的一些评论和答案，这些评论和答案对 dp 方法说不。但这是一个非常简单的 dp，类似于棒切割问题：

要得到本质：

int val[N][N];
int dp[N][T];

val[i][j]: numerical value of s[i..j] including both i and j

val[i][j] can be easily computed using dynamic programming approach in O(N^2) time

dp[i][j] : Minimum no of '+' symbols to be inserted in s[0..i] to get the required sum j

dp[i][j] = min( 1+dp[k][j-val[k+1][j]] ) over all k such that 0<=k<=i and val[k][j]>0

简单来说，要计算 dp[i][j]，您假设最后一个“+”符号的位置 k，然后递归 s[0 ..k]