hdu1331 Function Run Fun

题目：

Problem 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满足什么条件时就执行对应的递归式，但是这种情况对小的数据还可以，但是当a, b, c取稍微大一点儿的值就惨了。比如a=15, b=15, c=15. 但我们可以发现，只要把它递归的过程画出一小部分，我们就会发现其实这个过程中某些情况被递归了很多次，浪费了不少的时间。但是只要我们中途当第一次递归到这种情况时能把这个值存储下来，之后的递归再遇到这种情况时就直接用这个值，无需再把这种情况递归下去。这样我们就能节省许多时间。这就是记忆化搜索的基本思想吧。
而这道题实际上只要输入的a, b, c有一个小于等于0，结果就为1；如果a, b, c中其中有一个值大于20，结果就是当a=20,b=20,c=20时候的值。其他情况就采用记忆化搜索就可以了。

参考代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 20+5;

int a, b, c;
LL dp[N][N][N];

void init() {
    memset(dp, -1, sizeof(dp));
}

LL solve(int a, int b, int c) {
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (dp[a][b][c] >= 0) return dp[a][b][c];//记忆化搜索(如果搜索的值已经存在, 则无需再次递归搜索)
    //else if (a <= 0 || b <= 0 || c <= 0) return 1;
    else if (a > 20 || b > 20 || c > 20) dp[a][b][c] = solve(20, 20, 20);
    else if (a < b && b < c) dp[a][b][c] = solve(a, b, c-1) + solve(a, b-1, c-1) - solve(a, b-1, c);
    else dp[a][b][c] = solve(a-1, b, c) + solve(a-1, b-1, c) + solve(a-1, b, c-1) - solve(a-1, b-1, c-1);
    return dp[a][b][c];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    dp[0][0][0] = 1;

    while (cin >> a >> b >> c) {
        if (a == -1 && b == -1 && c == -1) break;
    
        LL ans;
        if (!(a <= 0 || b <= 0 || c <= 0) && (a > 20 || b > 20 || c > 20)) {
            ans = solve(20, 20, 20);
        }
        else ans = solve(a, b, c);
        cout << "w(" << a << ", " << b << ", " << c << ")" << " = " << ans << endl;
    }
    return 0;
}

转载于:https://www.jianshu.com/p/67c34e4d6cde