POJ #1579 Function Run Fun 记忆化搜索

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

题意

　　现在有一个三元组(a, b, c)，你要对 a、b、c 的大小进行分类讨论从而确定该三元组的值。这个算法很好实现，但是由于递归次数多所以执行时间很长。请你想一个执行时间尽可能短的办法来实现该算法。

Sample

　　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.

　　输入格式是三个整数组成的三元组，每个三元组占一行，直到读取到结束标志 -1 -1 -1 。输出格式直接看下面的图，我就不废话了。

　　Input:

　　output:

思路

　　这道题需要解决的是递归中用时过多的问题，为什么会用时过多呢？因为需要解决的子问题有很多都是重复的，即有太多的公共子问题。想想怎么样能少一点时间？那就是边递归边记录，已经记录的值就可以直接返回，这样就避免了递归时同一条数据的重复递归，这种技巧简称记忆化搜索，两个子问题有共同的子子问题，所以填个表，无需重复求解。　　　　

　　算法如下。多多注意边界判断与递归顺序。算法的最坏情况是每一次只让 a、b、c 其中一个的规模减一，所以算法的时间复杂度是 O(n_an_bn_c) 。

#include<iostream>
using std::cin;
using std::cout;
using std::endl;

int getTripleVal(int , int , int ); //查询给定三元组的值
const int MAX = 21;
int w[MAX][MAX][MAX]; //记忆数组

int main(void) {
    int a, b, c;
    while (cin >> a >> b >> c) {
        if ( a == -1 && b == -1 && c == -1) {
            return 0;
        }
        else {
            int res = getTripleVal(a, b, c);
            cout << "w(" << a << ", " << b << ", " << c << ")" << " = " << res << endl;
        }
    }
    return 0;
}//main

int getTripleVal(int a, int b, int c) {
    //边界条件
    if (a <= 0 || b <= 0 || c <= 0) {
        return w[0][0][0] = 1;
    }
    if (a >= MAX || b >= MAX || c >= MAX) {
        return getTripleVal(MAX-1, MAX-1, MAX-1);
    }
    
    //在记忆数组中查询 w[a][b][c]的值,实现记忆化搜索
    if (w[a][b][c]) {
        return w[a][b][c];
    }

    //求出结果并保存
    if (a < b && b < c) {
        return w[a][b][c] = getTripleVal(a, b, c-1) + getTripleVal(a, b-1, c-1) - getTripleVal(a, b-1, c);
    }
    
    //求出结果并保存
    return w[a][b][c] = getTripleVal(a-1, b, c) + getTripleVal(a-1, b-1, c) + getTripleVal(a-1, b, c-1) - getTripleVal(a-1, b-1, c-1); 
}//getTripleVal

View Code

————全心全意投入，拒绝画地为牢