POJ1579递归函数定义

Function Run Fun

http://poj.org/problem?id=1579

Description
We all love recursion! Don't we?

Consider a three-parameter recursive function w(a, b, c):

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.

Input
The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result.

Output
Print the value for w(a,b,c) for each triple.

Sample Input
1  1  1
2  2  2
10 4  6
50 50 50
-1 7  18
-1 -1 -1

Sample Output
w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

Source
Pacific Northwest 1999

很明显，这里的函数w定义就是个递归函数。不过w的递归过于复杂，如果直接按照题意编写模拟函数，肯定是TLE的。

这样在递归过程中记录一下中间结果，如果需要用到的时候则可以查表。由于有当a，b，c大于20的时候都视为20，则这个表是三维，最大元素为20的数组。

下面代码使用e数组作为表，每次先看是否在表中有对应结果，如果有则直接使用，没有就按照递归计算，计算完成后同时记录结果到表中。

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

int e[21][21][21];

int fun (int a, int b, int c)
{

    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return fun(20, 20, 20);
    if (a < b && b < c) {
        if (e[a][b][c]) return e[a][b][c];
        else 
            e[a][b][c] = fun(a, b, c-1) + fun(a, b-1, c-1) - fun(a, b-1, c);
    } else {
        if (e[a][b][c]) return e[a][b][c];
        else
            e[a][b][c] = fun(a-1, b, c) + fun(a-1, b-1, c) + fun(a-1, b, c-1) - fun(a-1, b-1, c-1);
    }

    return e[a][b][c];
}

int main (int argc, char const* argv[])
{
    int a, b, c;
    memset(e, 0, sizeof(e));

    while (1) {
        scanf("%d %d %d", &a, &b, &c);
        if (a == -1 && b == -1 && c == -1) {
            break;
        }

        printf("w(%d, %d, %d) = %d\n", a, b, c, fun(a, b, c));
    }

    return 0;
}