条件递归

Question

以下是来自spoj的问题的实现: - http://www.spoj.com/problems/COINS/

#include <stdio.h>

#define ll long long

ll arr[100000];

ll max(ll n)
{
    if(n < 49999)// Doubt
    {
        if(!arr[n])
            return arr[n] = max(n/2) + max(n/3) + max(n/4);
        else
            return arr[n];
    }
    else
        return max(n/2) + max(n/4) + max(n/3);
}


int main()
{
    ll n, c = 0, i;

    for(i = 0; i < 12; i++) // Also why 12 when the input can be <12
    {
        arr[i] = i;
    }

    while(scanf("%lld", &n) != EOF)
    {
        printf("%lld\n", max(n));

    }

    return 0;
}

为什么if条件包含n <49999？

Answer 1

除了前 20 多个值以及最大值和最小值之外，没有检查每种可能性：

我的期望是

arr[] 中的前 12 个条目是预先计算的，以帮助减少递归深度，但美元值与前 12 个条目的计算值不同。

对于硬币值 <= 49999，检查是否已经计算出该值，如果没有，则将硬币分成 /2 /3 /4 值并递归每个结果值。

该限制值 (49999) 可以扩展到 100000，因为这是 arr[] 数组的可用大小。

预设和保存到 arr[] 数组中是为了帮助减少执行时间和递归深度。

使用数组的目的是使函数可以立即返回任何先前计算的值（在发布的代码中，最多 49999）max()，而无需进一步递归。

我会稍微修改代码以获得更好的文档和稳健性以及更快的执行速度，如下所示：

#include <stdio.h>
#include <stdint.h>

#define MAX_ARRAY_LEN (100000)

uint32_t arr[ MAX_ARRAY_LEN ] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};

uint32_t max(uint32_t n)
{
    if(n < MAX_ARRAY_LEN)
    { // value of 'n' within the range of the learning array arr[]

        if(!arr[n] && n)
        { // then learning array arr[] not yet set
            return arr[n] = max(n/2) + max(n/3) + max(n/4);
        }

        else
        { // else learning array arr[] already set for 'this' value of 'n'
            return arr[n];
        }
    }

    else
    { // value of 'n' is greater than the learning array arr[]
        return max(n/2) + max(n/4) + max(n/3);
    }
} // end function: max


int main( void )
{
    uint32_t n;

    int status;
    while( (status = scanf("%u", &n)) == 1 && EOF != status)
    {
        if( 1000000000 >= n)
        {
            printf("%u\n", max(n) );
        }

        else
        {
            printf(" invalid value entered, must be in the range 0...1 000 000 000\n");
        } // end if
    } // end while

    return 0;
} // end function: main