快速遞歸遞歸得不到適當的結果

Question

給定一串數字，找到字符串等於某個目標數所需的最小添加數。每個添加都等價於在數字串的某個位置插入加號。

例如： 「1110」

目標3

返回3爲1 + 1 + 1 + 0 = 3需要3次加法。

「」

目標45

返回：8

「99999」

靶100

返回：-1

「382834」

返回：2

有3種方法得到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("%d\n", 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]; 
} 

我初始化我的memoized數組結果-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("%d\n", 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