Bytelandian Gold Coin,动态编程,解释？

Question

这有点不成熟,但我不得不问,

这里提到的Bytelandian金币问题 - http://www.codechef.com/problems/COINS/ ,据说是典型的DP问题,尽管我已经阅读了DP和递归的基础知识,但我发现很难理解它解,

 # include <stdio.h>
 # include <stdlib.h>

long unsigned int costArray[30][19];
unsigned int amount;

unsigned int currentValue(short int factor2,short int factor3)
{ 
    int j;
    unsigned int current = amount >> factor2;
    for(j=0;j<factor3;j++)
    current /= 3;
    return current;
}

long unsigned int findOptimalAmount(short int factor2,short int factor3)
{
     unsigned int n = currentValue(factor2,factor3);
    if(n < 12)
    { 
        costArray[factor2][factor3] = n;
        return (long unsigned int)n;
    }
    else
    { 
        if(costArray[factor2][factor3] == 0)
        costArray[factor2][factor3] = (findOptimalAmount(factor2+1,factor3) + findOptimalAmount(factor2,factor3+1) + findOptimalAmount(factor2+2,factor3));
        return costArray[factor2][factor3];
    }
}

int main()
{ 
    int i,j;
    while(scanf("%d",&amount) != EOF)
    { 
        for(i=0;i<30;i++)
        for(j=0;j<19;j++)
            costArray[i][j] = 0;
        printf("%lu\n",findOptimalAmount(0,0));
    }
    return 0;
} 

就像它的递归是如何工作的一样？costArray的大小如何确定为30x19？

另外,我如何才能提高解决问题的思路？

谢谢!

Answer 1

你的解释是正确的.但这里重要的一点仍然无法解释.这是f(n)定义的内容

max {f(n),f(n/2)+ f(n/3)+ f(n/4)}

最大的是f(n)的解.进一步挖掘,对于所有n <12 f(n)都大于f(n/2)+ f(n/3)+ f(n/4).这将成为递归的停止条件.虽然起初上面的表达似乎是一个微不足道的递归,但它的实现会导致效率非常低效(不能在spoj上接受的原因).

我们必须有一些如何存储函数f的中间值,使得递归实现的一部分将成为存储值的查找.

不幸的是,像fibbonaci系列的memoziation这样的值的直接存储对于这个例子是行不通的.因为在给定的程序中,n可以达到1000000000而且我们不能创建一个大小为1000000000的数组.所以这里有一个聪明的技巧,而不是直接为每个n存储子问题的值.我们知道n在每个阶段被细分为2(最多30次)和3(最多20次)(除以4只是除以2两次),因此我们将考虑尺寸为30x20的矩阵,其中索引为i的元素,j表示当用i乘2和j乘3时n的值.这样给定问题f(n)变换为F(0,0).现在我们在F上应用递归,并在每个阶段使用n值的memoization.

#include<stdio.h>
#define max2(a, b) ((a) > (b) ? (a) : (b))
unsigned long long ff[30][20] = {0};
unsigned long long n = 0;

/* returns value of n when divided by nthDiv2 and nthDiv3 */
unsigned long long current(int nthDiv2, int nthDiv3)
{
    int i = 0;
    unsigned long long nAfterDiv2 = n >> nthDiv2;
    unsigned long long nAfterDiv2Div3 = nAfterDiv2;
    for (i = 0; i < nthDiv3; i++)
        nAfterDiv2Div3 /= 3;
    return nAfterDiv2Div3;
}

unsigned long long F(int nthDiv2, int nthDiv3)
{
    /* if the value of n when divided by nthDiv2 and nthDiv3 is already calculated just return it from table */
    if (ff[nthDiv2][nthDiv3] != 0) 
        return ff[nthDiv2][nthDiv3];
    else {
        //calculate the current value of n when divided by nthDiv2 and nthDiv3 => F(nthDiv2, nthDiv3)
        unsigned long long k1 = current(nthDiv2, nthDiv3);
        if (k1 < 12) /* terminating condition */
            return k1;
        unsigned long long t = F(nthDiv2 + 1, nthDiv3) + F(nthDiv2, nthDiv3 + 1) + F(nthDiv2 + 2, nthDiv3); 
        /* Maximum of F(nthDiv2, nthDiv3) and F(nthDiv2 + 1, nthDiv3) + F(nthDiv2, nthDiv3 + 1) + F(nthDiv2 + 2, nthDiv3) */
        return ff[nthDiv2][nthDiv3] = max2(k1 , t); 
    }
}

int main()
{
    int i, j;
    while (scanf("%llu", &n) != EOF) {
        /* Every testcase need new Memoization table */
        for (i = 0; i < 30; i++)
            for (j = 0; j < 20; j++)
                ff[i][j] = 0;
        printf("%llu\n", F(0, 0));
    }
    return 0;
}