计数获得和的方式数，但有连续性限制。

Question

板球运动员可以在一个球中得分1，2，4或6。找出有多少种方法，球员可以得分总共"n“运行，而不触及3个连续的边界。注:得分4或6被视为边界。

我的解决办法是：

int *arr; //global array to save calculated ways
int waysUtil(int n, int boundaries){

     if(n==0)
        return 1;
     if(n<1)
        return 0;

    if(arr[n]>0)
        return arr[n];//if already calculated return the value
    int hit_one = waysUtil(n-1, 0);
    if(n-1 >=0) arr[n-1]= hit_one;
    int hit_two = waysUtil(n-2, 0);
    if(n-2 >=0) arr[n-2] = hit_two;
    int hit_four=0, hit_six=0;
    // for 4 and 6 check number of consecutive boundaries hit.
    //if less than two then calculate
    if(boundaries<2 ){

        hit_four = waysUtil(n-4, boundaries + 1);
        if(n-4 >=0) arr[n-4] = hit_four;
        hit_six = waysUtil(n-6, boundaries + 1);
        if(n-6 >=0) arr[n-6] = hit_six;

    }
    return hit_one + hit_two + hit_four + hit_six;
}


int ways(int score){
    arr =(int*)malloc(sizeof(int)*score);
    memset(arr, -1, sizeof(arr));
    int noOfWays = waysUtil(score, 0);
    free(arr);
    return noOfWays;
}

更好的解决办法可能吗？

Answer 1

这看上去不对：

memset(arr, -1, sizeof(arr));

这是将sizeof(int*)字节的arr设置为-1。它没有设置arr的全部内容。

你应该这么做：

int arr_size = sizeof(int)*score;
arr = (int*)malloc(arr_size);
memset(arr, -1, arr_size);

虽然正如@Andrea所指出的那样，这只是因为大多数体系结构和编译器都是基于两个互补号的。确实有一些这一规则的例外，如果它们对你有影响，你可能会知道。

Answer 2

Bug #1

在ways()中，您分配一个长度等于score的数组，如下所示：

arr =(int*)malloc(sizeof(int)*score);

然后打电话给waysUtil(score, 0)。但在waysUtil()中，您可以参考arr[n]，在本例中是n = score。因此，您正在读取数组的末尾。您需要分配一个比score大的数组来修复这个问题。

Bug #2

你的程序没有返回正确的答案。问题是，您的缓存arr只掌握了“有多少种方法可以达到这个分数而不触及3个边界”的答案。但是缓存中并没有包含“我在达到这个目标之前碰到了多少个边界”的信息。当你得了12分或更高时，问题就会发生。此时，得分8的缓存包含一个可能的4 + 4条目。但是代码将允许组合4 + 4 + 4在不应该计算的情况下被计数。

我写了我自己的程序来解决这个问题，得到了答案609的12分，而你的程序得到了答案610。所有分数超过12也得到了不同的答案。要解决这个问题，您的缓存应该是以下形式：

int arr[MAX_SCORE][3];

每个数组条目arr[score][b]应该包含“有多少种方法可以到达score，而以前的b条目都是边界的”？一旦你这样做了，你就可以正确地排除三行边界的情况。

提示:到达score的最终解决方案是arr[score][0] + arr[score][1] + arr[score][2]。

正确的解决方案

我已经用我在上一节中描述的技术编写了我自己的解决方案，但是我觉得在我给出解决方案之前，我应该给OP一个机会来修复他们的程序。但是，我将从我的程序中给出一些答案，以便OP能够验证正确性：

Score =  1, Ways = 1
Score =  2, Ways = 2
Score =  3, Ways = 3
Score =  4, Ways = 6
Score =  5, Ways = 10
Score =  6, Ways = 19
Score =  7, Ways = 33
Score =  8, Ways = 60
Score =  9, Ways = 106
Score = 10, Ways = 191
Score = 11, Ways = 340
Score = 12, Ways = 609
Score = 13, Ways = 1087
Score = 14, Ways = 1942
Score = 15, Ways = 3469
Score = 16, Ways = 6197
Score = 17, Ways = 11072
Score = 18, Ways = 19782
Score = 19, Ways = 35344