无聊做了的水题 题目描述 考虑如下的3参数递归函数w(a, b, c): 如果 a <= 0 或 b <= 0 或 c <= 0, 则 w(a, b, c)=1 如果 a > 20 或 b > 20 或 c > 20, 则 w(a, b, c)=w(20, 20, 20) 如果 a < b 且 b < c, 则 w(a, b, c)＝w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) 其它情况下 w(a, b ,c)=w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 这个函数很容易实现，但问题是，如果直接按照上述的结构实现，即使a、b和c的值不大 (比如, a = 15, b = 15, c = 15), 程序仍然需要几个小时才能完成大量的递归运算。 程序的输入为若干行整数，每行整数包含3个数值，分别对应a、b和c的值。程序输入以-1 -1 -1结束。设计一个程序，快速计算w(a, b, c)并给出结果。
分析 首先暴力直接按模型递归肯定下场就是GG 所以呢，我们可以仔细观察发现，这个递归固定的值只会有一个答案（唯一） 所以便有了一个想法：用三维数组储存，递归前判断是否为空即可
#include <iostream> #include <cstdio> #include <memory.h> using namespace std; int wa[21][21][21]; int w(int a, int b, int c) { if(a <= 0 || b <= 0 || c <= 0) { wa[0][0][0] = 1; return wa[0][0][0]; } if(a > 20 || b > 20 || c > 20) { if(wa[20][20][20] == -1) wa[20][20][20] = w(20, 20, 20); return wa[20][20][20]; } if(a < b && b < c) { if(wa[a][b][c] == -1) wa[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c); return wa[a][b][c]; } if(wa[a][b][c] == -1) wa[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1); return wa[a][b][c]; } int main() { int x, y, z; memset(wa, -1, sizeof(wa)); while(1) { scanf("%d%d%d", &x, &y, &z); if(x == -1 && y == -1 && z == -1) break; printf("w(%d, %d, %d) = %d\n", x, y, z, w(x, y, z)); } }