c - Bytelandian 金币，动态规划，解释？

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 的中间值，这样递归实现的一部分将成为存储值的查找。

不幸的是，像斐波那契数列的内存这样的值的直接存储对于这个例子是行不通的。因为在给定的程序中 n 可以达到 1000000000 而我们不能创建大小为 1000000000 的数组。所以这里有一个聪明的技巧，而不是直接为每个 n 存储子问题的值。我们知道 n 在每个阶段被 2(最多 30 次)和 3(最多 20 次) segmentation (除以 4 只是除以 2 两次)，所以我们将考虑一个大小为 30x20 的矩阵，其中索引 i 处的元素,j 表示 n 的值除以 i 次除以 2 和 j 次除以 3。这样给定的问题 f(n) 转换为 F(0,0)。现在我们对 F 应用递归并在每个阶段使用 n 值的内存。

#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;
}