对于快速求和递归，我的递归没有得到正确的结果

Question

给定一个数字字符串，求出该字符串所需的最小加法数，使其等于某个目标数。每次加法都相当于在字符串中的某个位置插入一个加号。

示例："1110"

目标3

当1+1+1+0=3时返回3需要3个加法。

"0123456789"

目标45

退货：8

"99999"

目标100

退货：-1

"382834"

100

退货：2

有三种方法可以得到100。它们分别是38+28+34、3+8+2+83+4和3+82+8+3+4。最低要求为2。

我尝试过这个问题，这是我的代码。我第一次考虑一个角色并得到结果。下一次我使用2个字符并得到结果，以此类推，直到我尝试了字符串大小的所有字符。我没有正确地进行递归。

    int min(int a,int b)
    {
        return a>b?b:a;
    }
    /* i is current index we are considering and sum is total number
     *of + required
     */
    int foo(char *a, int size, int i, int current_stock, int target, int sum){
        unsigned long long int mini = 1 << 30; /* huge number */
        int number=0, mul, m;
        int p = i;
        if (i+current_stock>size)
            return mini;
        if (target == 0)
            return sum;
        if (target < 0)
            return mini;
        mul = 1;
        /* make the multiplier */
        for (m=1;m<current_stock;m++) {
            mul *= 10;
        }
        /* make the number from i to current_stock
         * if the string is 123 and if i is 0 and current_stock is 2
         * then the number will be 12 */
        for (m=0;m<current_stock;m++) {
            number += (a[p]-'0')*mul;
            mul = mul/10;
            p++;
        }
        sum = sum + 1;
        for(m=current_stock;m<=size;m++) {
            mini = min(mini, foo (a, size, i+current_stock, m, target-number, sum));
        }
        return mini;
    }
    int main(void) {
        char a[] = "382834";
        printf("%d", foo(a, strlen(a), -1, 1, 100, 0));
        printf("%dn", strlen(a));
        return 0;
    }

Answer 1

我编码了你提到的确切解决方案，它似乎对我有效。只有一个变化，你不需要一直到所有字符，如果你已经越过目标，那么可以提前突破。

#define INFINITY 100000
long int result[20][1000];
long int solve(char *str,long int i,long int target){
    long int min=INFINITY;
    long int number=0,base=10;
    long int j=i;
    long int score1;
    //memoized result
    if(result[i][target]!=-2){
        return result[i][target];
    }
    //if target is achieved and string is finished
    if(i==strlen(str) && target==0){
        return 0;
    }
    // if string finished but target not achieved
    if(i==strlen(str)&& target!=0){
        return -1;
    }
    while(j<strlen(str)){
        long int digit=str[j]-'0';
        number=number*base+digit;
        if(number <=target){
            score1=solve(str,j+1,target-number);
            if(score1!=-1){
                if(j<(strlen(str)-1))
                    score1=score1+1;
                if(score1<min){
                    min=score1;
                }
            }
        }
        else{
            break;
        }
        j++;
    }
    if(min<INFINITY)
        result[i][target]=min;
    else
        result[i][target] = -1;
    return result[i][target];
}

对于非计算值，我正在用-2初始化我的内存化数组结果。我检查了所有给出的测试用例，它正在工作。请检查解决方案，并让我知道它是否合理。

Answer 2

我想@Naman让你找到了一个解决方案，但你工作太辛苦了。只需将第一个加号放在每个可能的位置，然后重复放置其余的。基本情况是所有数字都等于目标。在这种情况下，所需的加号数为零。

#include <stdio.h>
#include <string.h>
#define NO_SOLUTION (-1)
int find_min_plusses(int target, char *digits, int n_digits) {
  int min = NO_SOLUTION, val = 0, i;
  for (i = 0; i < n_digits - 1; i++) {
    val = val * 10 + (digits[i] - '0');
    if (val > target) return min;
    int rest = find_min_plusses(target - val, digits + i + 1, n_digits - i - 1);
    if (rest != NO_SOLUTION && (min == NO_SOLUTION || rest + 1 < min))
      min = rest + 1;
  }
  val = val * 10 + (digits[i] - '0');
  return val == target ? 0 : min;
}
int main(int argc, char *argv[]) {
  int target;
  if (argc == 3) {
    if (sscanf(argv[1], "%d", &target) != 1) return 1;
    int min = find_min_plusses(target, argv[2], strlen(argv[2]));
    printf("%dn", min);
  }
  return 0;
}

在这里你可以观看它的运行。每一行都是一个电话。

./a.out 100 382834
tgt=100,digits=382834,n_digits=6
tgt=97,digits=82834,n_digits=5
tgt=89,digits=2834,n_digits=4
tgt=87,digits=834,n_digits=3
tgt=79,digits=34,n_digits=2
tgt=76,digits=4,n_digits=1
tgt=4,digits=4,n_digits=1
tgt=61,digits=34,n_digits=2
tgt=58,digits=4,n_digits=1
tgt=15,digits=834,n_digits=3
tgt=7,digits=34,n_digits=2
tgt=4,digits=4,n_digits=1
tgt=62,digits=2834,n_digits=4
tgt=60,digits=834,n_digits=3
tgt=52,digits=34,n_digits=2
tgt=49,digits=4,n_digits=1
tgt=34,digits=34,n_digits=2
tgt=31,digits=4,n_digits=1
2